When you use Gaussian elimination to solve a homogeneous system of linear equations, you end up with "pivot variables" and "non-pivot variables". The non-pivot variables have the property that they can each be chosen freely, and once specified, they uniquely determine a solution to the equation.
I'm looking for a characterization of these free variables that depends on the operator $A$ and the choice of basis $\{b_i\}$ but does not refer to the Gaussian elimination process itself.
For example, you could look at the equation $x_1 + x_2 + x_3 = 0$ and determine that any two of the variables can be chosen freely and uniquely determine the third, whereas one variable is insufficient and three variables is too many to be chosen freely.
For another example, take $$x_0 + x_1 + x_2 = 0\\ x_0 + x_3 + x_4 = 0.$$
The set $\{x_0, x_2,x_3\}$ consists of variables that can be freely chosen and uniquely determine a solution. In contrast, $\{x_0,x_1,x_2\}$ cannot be chosen freely, despite having three variables.
My goal is to find a test that can identify which sets of variables uniquely and freely determine a solution. My starting point is Gaussian elimination, where the non-pivot rows show you one such subset of variables. I would like to be able to characterize all such sets of variables, without reference to Gaussian elimination.
Here's my attempt.
- Let $A$ be a matrix with basis $B=\{x_1,\ldots,x_m\}$.
- Reduce $A$ using Gaussian elimination. Let $N$ be the submatrix of $\text{rref}(A)$ consisting of the non-pivot columns. I believe $N$ is equivalent to the kernel map for $A$ expressed in our basis, in which case it can be defined without referring to the elimination process—is that right?
- Consider a subset of variables $E\equiv \{e_1,\ldots, e_d\}\subseteq \{x_1,\ldots,x_m\}$. These variables might have the desired property, or not.
- To determine whether $E$ has the desired property (i.e. the variables of $E$ may be chosen freely, and when they are chosen, they uniquely determine a solution to the homogeneous equation.), consider the linear map $Q:\mathbb{R}^d \hookrightarrow \mathbb{R}^m$ induced by the inclusion of $E$ into $B$. The requirement is that $QN$ is the identity map $I_{d\times d}$. (Or maybe just that $QN$ is invertible.)
- I got this definition by trying to formalize the idea that each basis vector in $E$ meets (has a nonzero dot product with) the columns of the null matrix in exactly one unique place. That is, it forms a kind of identity sub matrix. Because it meets each vector exactly once, we know that the variables can be chosen freely and uniquely determine a solution.
Is this right? Is there a better formulation? Thanks for your help.
P.S. For example of how to apply this method, consider the following separate problems $A_1 = [1,1]$, versus $A_2 = [1,0]$. Each of these problems is a system with two variables and one equation $(A : \mathbb{R}^m\rightarrow \mathbb{R}^n$ with $m=2$, $n=1$). Each has a one-dimensional space of solutions (the nullity of $A$ is $d=1$).
Our basis of variables $B$ consists of the standard basis vectors. Any set of $d=1$ vectors (i.e. the singleton sets $\{e_1\}$, $\{e_2\}$) is a candidate for being a complete set of free variables. To test them, we consider the inclusions of $e_1$ or $e_2$ from $\mathbb{R}^m \hookrightarrow \mathbb{R}^d$:
$$E_1 = \begin{bmatrix}1 & 0\end{bmatrix}$$ $$E_2 = \begin{bmatrix}0 & 1\end{bmatrix}$$
We will need the kernel maps of $A_1$ and $A_2$. These are maps $\mathbb{R}^d\rightarrow \mathbb{R}^m$.
The kernel of the matrices $A_1$ and $A_2$ are, respectively:
$$K_1 = \begin{bmatrix}1\\ -1\end{bmatrix}\qquad u\mapsto \langle u,-u\rangle$$
$$K_2 = \begin{bmatrix}0 \\ 1\end{bmatrix}\qquad v \mapsto \langle 0, v\rangle$$
When we test whether $E_1$ and $E_2$ are free variables for the first matrix, we find:
$$E_1K_1 = [1]\\ E_2K_1 = [-1]$$
Whereas for the second matrix, we find:
$$E_1K_2 = [0]\\ E_2K_2 = [1]$$
By examining which of these is an invertible transformation $\mathbb{R}^d\rightarrow \mathbb{R}^d$, we have determined that $\{e_1\}$ and $\{e_2\}$ are complete unique variable sets for the first system $A_1$, but only $\{e_2\}$ is a complete unique variable set for the second system $A_2$.
Proof: First, we'll establish uniqueness then minimality.
Uniqueness. The chosen columns of $N^\prime$ comprise a $d\times d$ matrix $D$. If the columns of $D$ are linearly independent, then $D$ is invertible (injective). $D$ represents a transformation from the $d$ parameters of the null space to the specific set of $d$ variables you selected for $D$.
To see this, note that $D$ is a composition of the $d\times m$ matrix $E$ formed by choosing $d$ rows of the identity matrix $I_m$, and the matrix $N^\prime$. The composite $D=EN^\prime$ therefore represents a transformation taking the $d$ variables of the null space to the $m$ original variables of a full, uniquely determined solution, then forgetting (quotienting out) all but $d$ of those original variables. If this process is reversible, then the $d$ original variables can be mapped back to the $d$ parameters of the null space, which then uniquely determine a solution because $N^\prime$ is a basis.
Minimality. The null space (solution space) has $d$ dimensions; therefore it takes $d$ independent parameters to determine a solution. So if a set of $d$ variables uniquely determines a solution, that set is minimal.
And this theorem is independent of the Gauss-Jordan elimination process: Although we used Gauss-Jordan elimination to find $N^\prime$, we didn't need to. $N^\prime$ is a representation of the kernel map of the operator $A$, which is uniquely defined independent of basis. The basis (choice of variables) is used only to define the "column choosing" matrices $E$, which are basis-dependent mappings from the original set of variables.