### SOLVING SYSTEMS OF LINEAR EQUATIONS:

A system of linear equations, such as

\begin{align} a_{11}\,x_1\;+\;a_{12}\,x_2\;+\;\cdots\;+\;a_{1n}\,x_n&\;=\;b_1\\[2ex] a_{21}\,x_1\;+\;a_{22}\,x_2\;+\;\cdots\;+\;a_{2n}\,x_n&\;=\;b_2\\[2ex] \vdots\\[2ex] a_{m1}\,x_1\;+\;a_{m2}\,x_2\;+\;\cdots\;+\;a_{mn}\,x_n&\;=\;b_m\\[2ex] \end{align}

can be summarized as $$A\,\vec x =\vec b,$$ where $$A =\left [ a_{ij} \right ]_{i=1,\dots,m\text{ and }j=1,\dots,n}.$$

If on the RHS, we have all zeroes, $$A\vec x=\vec 0,$$ we have the associated homogeneous linear system. The original system is inhomogeneous.

#### Row operations allowed:

1. Switch rows
2. Add a multiple of one row to another
3. Multiply a row by a constant different to zero.

$\left[\begin{array}{rrr|r} 1 & 1 & 3 & 1 \\ 1 & -1 & -1 & 5 \\ 2 & 0 & 2 & 6 \end{array}\right]$

can be transformed into

$\left[\begin{array}{rrr|r} \bbox[5px,border:2px solid red]{1} & 1 & 3 & 1 \\ 0 & \bbox[5px,border:2px solid red]{1} & 2 & -2 \\ 0 & 0 & 0 & 0 \end{array}\right]$

which is the matrix in echelon form with the ones in the red square being the pivots. However, it doesn’t have to have pivots equal to $$1,$$ they just have to be different than $$0.$$ Below these pivots there are only zeroes. Pivots move down and to the right.

The reduced echelon form $$(\text{rref})$$ has all pivots as ones, and the entries above pivots are zero (not just below):

$\left[\begin{array}{rrr|r} \bbox[5px,border:2px solid red]{1} & 0 & 1 & 3 \\ 0 & \bbox[5px,border:2px solid red]{1} & 2 & -2 \\ 0 & 0 & 0 & 0 \end{array}\right]$

The reduced echelon form is unique (not so the echelon form).

Reading the solution in standard form:

\begin{align} 1\,x_1 \;+\; 0\,x_2 \;+\; 1\,x_3\;&=\;3 \\[2ex] 0\,x_1 \;+\; 1\,x_2 \;+\; 2\,x_3\;&=\;-2 \\[2ex] \end{align}

Now, $$x_1$$ and $$x_2$$ are pivot variables, while $$x_3$$ is a free variable. So we solve for the pivot variables:

\begin{align} x_1 &= 3-x_3 \\[2ex] x_2 &= -2 -2x_3 \end{align}

and the free variable:

$x_3 = x_3$

In vector form

$\vec x = \begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}= \begin{bmatrix}3\\-2\\0 \end{bmatrix}+x_3\,\begin{bmatrix}-1\\-2\\1\end{bmatrix}$

which is the equation for a line (a point plus a direction vector), and is equivalent to a particular solution (the vector $$\begin{bmatrix}3\\-2\\0\end{bmatrix}$$) plus a general solution. The general solution has the property $$A\vec x =\vec 0$$, i.e. it is the null space of $$A.$$

The vector $$\begin{bmatrix} -1\\-2\\1\end{bmatrix}$$ is orthogonal to each one of the rows of $$A.$$ It is in the $$\vec x \in \text{span}\left(\vec A_1,\dots,\vec A_n \right)$$ (the span of the row vectors).

It is worth noting that the dimension of the null space of $$A$$ is $$n-r$$ (number of columns minus the rank), which in this case is just $$3-2=1.$$

#### FINDING BASIS FOR SUBSPACES IN ECHELON AND RREF:

Starting with an example - matrix $$A:$$

$A = \begin{bmatrix} 1&-1&2&3&0\\ 2&-2&-1&1&5\\ 1&-1&1&2&1\\ -1&1&3&2&-5 \end{bmatrix}$

and augmenting the matrix with “$$b$$’s”, allows keeping track of elementary row operations:

$\left[\begin{array}{rrrrr|r} 1&-1&2&3&0&b_1\\ 2&-2&-1&1&5&b_2\\ 1&-1&1&2&1&b_3\\ -1&1&3&2&-5&b_4 \end{array}\right]$

We bring out the pivot columns…

$\left[\begin{array}{rrrrr|r} 1&-1&2&3&0&b_1\\ 0&0&-5&-5&5&b_2-2b_1\\ 0&0&-1&-1&1&b_3-b_1\\ 0&0&5&5&-5&b_4+b_1 \end{array}\right]$

…changing rows to avoid fractions:

$\left[\begin{array}{rrrrr|r} 1&-1&2&3&0&b_1\\ 0&0&1&1&-1&b_1-b_3\\ 0&0&0&0&0&3b_1 +b_2-5b_3\\ 0&0&0&0&0&-4b_1+5b_3+b_4 \end{array}\right]$

and ending with a non-reduced echelon form:

$\text{ef}(A)=U=\begin{bmatrix} 1&-1&2&3&0\\ 0&0&1&1&-1\\ 0&0&0&0&0\\ 0&0&0&0&0 \end{bmatrix}$

with the matrix of elementary row operations:

$E= \begin{bmatrix} \text{takes first row unaltered:}&1&0&0&0\\ \text{subtacts third row from first:}&1&0&-1&0\\ \text{takes (3 x 1st) + (2nd) - (5 x 3rd) row:}&3&1&-5&0\\ \text{takes (-4 x 1st) + (5x3rd) + (1x4th):} &-4&0&5&1 \end{bmatrix}$

Side by side:

$U\vert E=\left[\begin{array}{rrrrr|rrrr} 1&-1&2&3&0&1&0&0&0\\ 0&0&1&1&-1&1&0&-1&0\\ 0&0&0&0&0&3&1&-5&0\\ 0&0&0&0&0&-4&0&5&1 \end{array}\right]$

These are the constraint equations:

$\left\{ \begin{array}{c} 3b_1 +1b_2-5b_3 +0b_4&= 0 \\ -4b_1+0b_2+5b_3+1b_4 &=0 \end{array} \right.$ For instance, taking the first column vector of $$\vec a_1=\begin{bmatrix}1\\2\\1\\-1\end{bmatrix}$$ and carry out the dot product with the first constraint equation, $$\begin{bmatrix}3&1&-5&0 \end{bmatrix}\cdot\begin{bmatrix}1\\2\\1\\-1\end{bmatrix}=0.$$ Same with the second constraint equation: $$\begin{bmatrix}1&2&1&-1\end{bmatrix}\cdot \begin{bmatrix}-4\\0\\5\\1\end{bmatrix}=0.$$

The reduced row echelon can be obtained without keeping track of $$b$$’s, and just to read out the general solution. To get it, we subtract two times the second row from the first:

$\text{rref}(A)=\begin{bmatrix} 1&-1&0&1&2\\ 0&0&1&1&-1\\ 0&0&0&0&0\\ 0&0&0&0&0 \end{bmatrix}$

From this rref, the pivot columns are expressed in terms of the free variables, which only depend on themselves, to obtain the general solution, as well as a basis of the null space of $$A.$$ The combinations of column vectors elementwise in the solution of the homogeneous system of equations can be expressed as

\begin{align} 1x_1 - 1x_2 +0x_3+1x_4+2x_5 &=0\\ 0x_1 + 0x_2 +1x_3+1x_4-1x_5 &=0\\ \end{align}

The pivot columns are $$x_1$$ and $$x_3$$, and we want to express every entry in terms of the free variables $$x_2, x_4, x_5:$$

\begin{align} x_1&=x_2 -x_4-2x_5\\ x_2&=x_2\\ x_3&=-x_4+x_5\\ x_4 &= x_4\\ x_5&=x_5 \end{align}

#### NULL SPACE:

The general solution of $$A\vec x =\vec 0$$ is:

$\vec x= x_2 \,\begin{bmatrix}1\\1\\0\\0\\0\end{bmatrix}+x_4\,\begin{bmatrix}-1\\0\\-1\\1\\0\end{bmatrix}+x_5\,\begin{bmatrix}-2\\0\\1\\0\\1\end{bmatrix}$

and the basis of the null space can be read directly from the rref matrix:

$\text{rref}(A)=\begin{bmatrix} 1&-1&0&1&2\\ 0&0&1&1&-1\\ 0&0&0&0&0\\ 0&0&0&0&0 \end{bmatrix}\to\begin{bmatrix} \text{pivot}&\text{free}&\text{pivot}&\text{free}&\text{free}\\\bbox[5px,border:2px solid red]1&\bbox[5px,border:2px solid magenta]{+1}&0&\bbox[5px,border:2px solid green]{-1}&\bbox[5px,border:2px solid orange]{-2}\\ 0&0&\bbox[5px,border:2px solid red]1&\bbox[5px,border:2px solid green]{-1}&\bbox[5px,border:2px solid orange]{+1}\\ 0&0&0&0&0\\ 0&0&0&0&0 \end{bmatrix}$

the null space has basis vectors with $$5$$ elements, which will incorporate the magenta elements above:

$\begin{pmatrix}\begin{bmatrix}0\\1\\0\\0\\0 \end{bmatrix}, \begin{bmatrix}0\\0\\0\\1\\0 \end{bmatrix},\begin{bmatrix}0\\0\\0\\0\\1 \end{bmatrix} \end{pmatrix} \to \begin{matrix}\text{pivot }\to\\\text{free }\to\\\text{pivot }\to\\\text{free }\to\\\text{free }\to\\\end{matrix} \begin{pmatrix}\begin{bmatrix}\bbox[5px,border:2px solid magenta]{+1}\\1\\0\\0\\0 \end{bmatrix}, \begin{bmatrix}\bbox[5px,border:2px solid green]{-1}\\0\\\bbox[5px,border:2px solid green]{-1}\\1\\0 \end{bmatrix},\begin{bmatrix}\bbox[5px,border:2px solid orange]{-2}\\0\\\bbox[5px,border:2px solid orange]{+1}\\0\\1 \end{bmatrix} \end{pmatrix}$

These vectors are the solution to the homogeneous system of linear equations $$A\vec x=\vec 0,$$ and span the null space of $$A$$, plus they are linearly independent. Hence they are a $$\color{blue}{\text{basis of the null space}}.$$ It has a dimension of $$3$$, corresponding to the number of free variables. Vectors in the null space of $$A$$ are orthogonal to the rows of $$A$$, an express what linear combinations of the columns of $$A$$ result in $$\vec 0.$$

The dimension of the null space $$N(A)$$ is the number of columns minus the rank: $$n-r$$.

#### COLUMN SPACE:

A $$\color{blue}{\text{basis of the column space}}$$ can be obtained from the pivot columns of the original matrix $$A,$$ i.e. $$\begin{bmatrix}1&2\\2&-1\\1&1\\1&3\end{bmatrix}.$$

Observe that the column space of $$A$$ is precisely the span of the column vectors, and also the $$\vec b$$’s for which the system of linear equations $$A\vec x = \vec b$$ is consistent (i.e. it has one or more solutions):

\begin{align} \text{Col }(A) &=\text{Span }\left(\{\vec a_1, \vec a_2,\dots , \vec a_n\} \right)\\[2ex] &=\{\vec b: \; A\,\vec x=\vec b\text{ is consistent}\} \end{align}

and for these equations to be consistent the constraint equations have to hold. Or in other words, if a vector is in the null space of $$\vec w\in A^\top$$, then $$\vec w \vec b = \vec 0.$$

The dimension of the column space $$\text{Col}(A)$$ is the rank $$r$$.

#### ROW SPACE:

A $$\color{blue}{\text{basis of the row space}}$$ can be found in the non-zero rows of any echelon form: $$\begin{bmatrix}1&0\\-1&0\\2&1\\3&1\\0&-1\\\end{bmatrix}:$$

$U\vert E=\left[\begin{array}{rrrrr|rrrr} \bbox[5px,border:2px solid magenta]1&\bbox[5px,border:2px solid magenta]{-1}&\bbox[5px,border:2px solid magenta]2&\bbox[5px,border:2px solid magenta]3&\bbox[5px,border:2px solid magenta]0&1&0&0&0\\ \bbox[5px,border:2px solid red]0&\bbox[5px,border:2px solid red]0&\bbox[5px,border:2px solid red]1&\bbox[5px,border:2px solid red]1&\bbox[5px,border:2px solid red]{-1}&1&0&-1&0\\ 0&0&0&0&0&3&1&-5&0\\ 0&0&0&0&0&-4&0&5&1 \end{array}\right]$

The dimension of the row space $$\text{Row}(A)$$ is the rank $$r$$.

#### LEFT NULL SPACE:

A $$\color{blue}{\text{basis of the null space of the transposed (left null space) }N(A^\top)}$$ can be obtained by transposing the bottom rows of $$E$$

$U\vert E=\left[\begin{array}{rrrrr|rrrr} 1&-1&2&3&0&1&0&0&0\\ 0&0&1&1&-1&1&0&-1&0\\ 0&0&0&0&0&\bbox[5px,border:2px solid magenta]{3}&\bbox[5px,border:2px solid magenta]1&\bbox[5px,border:2px solid magenta]{-5}&\bbox[5px,border:2px solid magenta]{0}\\ 0&0&0&0&0&\bbox[5px,border:2px solid red]{-4}&\bbox[5px,border:2px solid red]0&\bbox[5px,border:2px solid red]5&\bbox[5px,border:2px solid red]1 \end{array}\right]$

corresponding to the zero rows in the echelon form: $$\begin{bmatrix}3&-4\\1&0\\-5&5\\0&1\end{bmatrix}.$$ Vectors in the null space of $$A^\top$$ express what cominations of the rows of $$A$$ result in $$\vec 0.$$

Since in the null space of $$A^\top$$ (the left null space) we are looking at vectors that $$A^\top \,y=\vec 0\implies y^\top\,A =\vec 0^\top$$, or referring back to the matrix example above, where

\begin{align} E\,A &=U\2ex] \begin{bmatrix}\\ \\ 3&1&-5&0\\-4&0&5&1\end{bmatrix}\;A &=\begin{bmatrix}\\ \\ 0&0&0&0\\0&0&0&0\end{bmatrix} \end{align} The components of the null space of $$A^\top$$ are the coefficients of the constraint equations (above), and are orthogonal to the column vectors of $$A$$ because for each one of them, a vector in the left null space expresses the combinations of each entry (rows) that result in zero. The dimension of the left null space $$N(A^\top)$$ is the number of rows minus the rank $$m-r$$. Here is a quick geometric illustration with the matrix \[A = \begin{bmatrix} 1&2&3\\4&5&6\end{bmatrix}

which has the rref

$A = \begin{bmatrix} 1&0&-1\\0&1&2\end{bmatrix}$

with two pivot columns (leading $$1$$’s), and with a column and row space of dimension $$2$$ (the rank), a null space of $$n-r=3-2=1$$, and a left column space of dimension $$m-r=2-2=0.$$

A basis of the $$N(A)$$ is $$\left\{ \begin{bmatrix}1\\-2\\1 \end{bmatrix}\right\}$$, immediately culled from the rref. There is, naturally, no basis for the left null space.

The column space lives in $$\mathbb R^2$$, whereas the row and null spaces live in $$\mathbb R^3:$$