# Variable elimination in linear programming

I have a linear program of the form

$$\underset{P,\;g}{\text{Minimize}}\hspace{3mm}c^Tg$$ \begin{align} \hspace{17mm}\text{Subject to}\hspace{3mm}AP_{\cdot,j}&=\begin{bmatrix} -g\\ d \end{bmatrix}\\ P_{ii}&=0\\ |P_{\cdot,j}|&\leq P_{\max}\\ g&\leq G_{\max}\\ g&\geq 0 \end{align}

with variables: $g\in{\bf R}^k$, $P\in{\bf R}^{n\times n}$,

and problem data: $c\in{\bf R}^k$, $A\in{\bf R}^{m\times n}$, $d\in{\bf R}^{m-k}$, $P_{\max}\in{\bf R}^n$, $G_{\max}\in{\bf R}^k$.

I'm only interested in $g$, and thus I was wondering if there was a way to somehow eliminate the variable $P$, thereby significantly reducing the dimension of the search space.

If $A$ is invertible it's almost certainly doable.

If $A$ has a left-inverse it might be doable.

If $A$ has more columns than rows and full row-rank it might be doable.

If $A$ has more columns than rows without full row-rank then I don't think it's doable, however this is the case I'm most interested in.

• Does $P_{\cdot,j}$ denote the $j$th column of $P$? If so, if $A$ is invertible (the first constraint has a unique solution) or has more rows than columns and is full rank (the first constraint is over-determined, allowing for at most one solution), then all of the $P_{\cdot,j}$ will be the same, and the second (trace) and third (norm) constraint can not be satisfied independently of the first one -- i.e., the solution $P$ of the first constraint is what it is, and may or may not satisfy these constraints. This doesn't look like a well-posed problem to me. – Wolfgang Bangerth Jan 17 '17 at 16:54
• @WolfgangBangerth Yes $P_{\cdot,j}$ is the $j$th column of $P$. In my particular case $A$ has more columns than rows, not more rows than columns. But I was curious about the case where $A$ was square and invertible just to get a baseline read on the problem. Unfortunately in my particular case $A$ also has rank $m-1$ (being the incidence matrix for a connected directed graph), and thus does not have full row rank. What about the problem makes it not well-posed? – Thoth Jan 17 '17 at 17:07
• I was suggesting that it is not well posed if $A$ had full row rank. In that case, the $P_{\cdot,j}$ would all be the same since they solve the same linear problems, and they would be uniquely determined. Whether $P_{ii}=0$ is then dependent on how the solution of the linear system looks like, same for the third constraint. Unless you get extremely lucky, the unique solutions $P_{\cdot,j}$ do not satisfy these constraints, and consequently the problem has no solution -- i.e., it is not well posed. – Wolfgang Bangerth Jan 17 '17 at 20:20
• On the other hand, if $A$ has rank less than $n$, and assuming that the right hand side of the first constraint is in the image of $A$, then the $P_{\cdot,j}$ simply lie in the null space. It may be possible, in that case, to satisfy the second and third constraint, assuming that $P_\text{max}$ is sufficiently large (namely, at least as large as the minimum norm solution of the first constraint). – Wolfgang Bangerth Jan 17 '17 at 20:23