I have a system of linear equations. The system is not well-constrained (I have more parameters than independent equations). What is the easiest way to identify the subset of parameters that are well-constrained?
For a simple example, if I have the system:
$5a + 6b + 7c + 8d= 100$
$9a - 18b +3c - 4d = -50$
$6d + 5e = -25$
$3d - 4e = 62$
$d$ and $e$ are well-constrained but $a$, $b$ and $c$ are not. How can I take a system like this of arbitrary size and figure out which parameters in that system are well-constrained?
$\endgroup$ 11 Answer
$\begingroup$Honestly, I would suggest that you are taking a somewhat limited definition of "well-constrained" here. So first let's attempt to address that definition specifically, and then suggest a better way of looking at it.
To identify individual well-constrained variables, you can construct the kernel or null space of the coefficient matrix. Any variable that does not appear in that basis is well-constrained, according to your definition. For instance, in the example above, the coefficient matrix is $$A\triangleq \begin{bmatrix} 5 & 6 & 7 & 8 & 0 \\ 9 & -18 & 3 & -4 & 0 \\ 0&0&0& 6 & 5 \\ 0&0&0& 3 & -4 \end{bmatrix}$$ The rank of this matrix is 4, so the null space is spanned by exactly one vector: $$Z=\begin{bmatrix}3 \\ 1 \\ -3 \\ 0 \\ 0 \end{bmatrix}$$ Since the fourth and fifth elements of $Z$ are zero, those variables are well-constrained.
The kernel may require more than one vector to describe its basis---or if these basis vectors are assembled into a single matrix $Z$, that matrix may have more than one column. In that case, the well-constrained variables are those corresponding to an entire row of zeros in $Z$.
As I said above, the rank of $A$ is 4. That means the linear system $Ax=b$ effectively constrains four directions of the solution vector $x$. And yet, only $2$ of the variables are well-constrained, according to your definition. Note the distinction: $4$ directions are constrained, but only $2$ variables are. Is there a way to bring these two definitions together; that is, find $4$ variables that are "well-constrained" in some sense?
Yes, there is. To do so, we compute the reduced row echelon form of $A$. The RREF is computed by performing Gaussian elimination on the rows of the matrix, and doing some additional elimination to reach a unique canonical form; see the Wikipedia link I've provided. The RREF of your example is $$R =\begin{bmatrix} 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1/3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$ Because this matrix is formed via Gaussian elimination on the rows, we have $A=BR$ for some nonsingular square matrix $B$, but we do not need to know $B$ to proceed.
Looking at this matrix $R$, you will see that columns 1, 2, 4, and 5 are the columns of an identity matrix. We call the variables corresponding to those columns---$a$, $b$, $d$, and $e$---as the bound variables, and they correspond in an important sense to your "well-constrained" variables. What this means is that once you have selected a value for $c$, all four of the other variables are uniquely determined. That's not quite the same as your definition of "well-constrained", but it's a more standard way of looking at the problem.
Note that the choice of "bound" variables depends on the ordering of the columns. So for instance, if we swapped the columns for $c$ and $a$, the RREF would identify $b$, $c$, $d$, and $e$ as bound.
It's not difficult to recover your original definition of "well-constrained" from the RREF. Note that rows 3 and 4 have only one nonzero each in columns 4 and 5, respectively. From this we can see that $d$ and $e$ can be determined even without selecting a value for $c$. They are indeed well-constrained.
$\endgroup$ 2
