NOTES ON STATISTICS, PROBABILITY and MATHEMATICS

Gauss Jordan Elimination and 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:\)

Home Page

NOTE: These are tentative notes on different topics for personal use - expect mistakes and misunderstandings.