next up previous
Next: Solving Linear Systems by Up: Solving Linear Algebraic Equations Previous: LU Decomposition

Fundamental theorem of linear algebra

An M by N matrix ${\bf A}\in R^{M\times N}$ can be expressed in terms of either its $N$ M-D column vectors ${\bf c}_j$ or its $M$ N-D row vectors ${\bf r}_i^T$:

{\bf A}=\left[\begin{array}{ccc}a_{11}&\cdots&a_{1N}\\
...array}{c}{\bf c}^T_1 \vdots {\bf c}^T_N\end{array}\right]

where ${\bf r}_i$ and ${\bf c}_j$ are respectively the ith row vector and jth column vector (note that through out the text, all vectors are assumed to be vertical):

{\bf c}_j=\left[\begin{array}{c}a_{1j} \vdots a_{Mj}\en...
{\bf r}_i^T=[a_{i1},\cdots,a_{iN}]

The $M$ by $N$ matrix ${\bf A}$ in the linear function (a transformation) ${\bf f}({\bf x})={\bf A}{\bf x}$ maps an N-D vector in the domain of the function, ${\bf x}\in \mathbb{R}^N$, to an M-D vector in the codomain of the function, ${\bf Ax}\in R^M$.


The fundamental theorem of linear algebra concerns the following four fundamental subspaces associated with any $M\times N$ matrix ${\bf A}$ with rank $R=rank({\bf A})\le \min(M, N)$, there are $R$ independent columns and rows.

The bases of these four subspaces can be found by converting ${\bf A}$ into the reduced row echelon form (rref). by the elementary row operations (row reduction).

Example 0:

\begin{displaymath}{\bf A}=\left[\begin{array}{rrr}1&2&5 2&3&8 3&1&5\end{array}\right] \end{displaymath}

By elementary row operations, we can convert ${\bf A}$ into the rref form:

\begin{displaymath}{\bf A}=\left[\begin{array}{ccc}1&2&5 2&3&8 3&1&5\end{arr...
...left[\begin{array}{ccc}1&0&1 0&1&2 0&0&0\end{array}\right] \end{displaymath}

We see that ${\bf c}_3={\bf c}_1+2{\bf c}_2$. Alternatively, if we define another matrix ${\bf A}'$ by switching the 2nd and 3rd columns of ${\bf A}$, we have

{\bf A}'=\left[\begin{array}{ccc}1&5&2 2&8&3 3&5&1\end{...
...begin{array}{ccc}1&0&-0.5 0&1&0.5 0&0&0\end{array}\right]

Now we have ${\bf c}_3=-0.5{\bf c}_1+0.5{\bf c}_2=({\bf c}_2-{\bf c}_1)/2$. We see that in either case, the column space is a 2-D plane spanned by any two of the three column vectors.

The $R=rank({\bf A})$ columns in the rref matrix that contain a single 1, called a pivot element, are the pivot columns, and the $R$ corresponding rows each containing a pivot are the pivot rows, which span the R-D row space $R({\bf A})$. However, the columns of ${\bf A}$ are changed by the row reduction operations and the pivot columns of the rref form do not span the column space $C({\bf A})$.

The number of pivots in the rref form is the rank of ${\bf A}$, the number of independent rows or columns in ${\bf A}$, i.e., the dimension of both $C({\bf A})$ and $R({\bf A})$:

\begin{displaymath}dim\;C({\bf A})=dim\;R({\bf A})=rank({\bf A}) \end{displaymath}

The $R$ pivot rows correspond to the independent equations in the system ${\bf A}{\bf x}={\bf b}$, while the remaining $M-R$ non-pivot rows containing all zeros are not independent. They don't play any role in the equation system ${\bf A}{\bf x}={\bf b}$, as they map any ${\bf x}$ to ${\bf0}$.

Example 1:

Solve the following homogeneous equation

\begin{displaymath}{\bf A}{\bf x}=\left[\begin{array}{ccc}1&2&5 2&3&8 3&1&5\...
=\left[\begin{array}{c}0 0 0\end{array}\right]
={\bf0} \end{displaymath}

Applying the elementary row operations, we get

\left[\begin{array}{ccc}1&2&5 2&3&8 3&1&5\end{array}\rig...
=\left[\begin{array}{c}0 0 0\end{array}\right]

In this rref form, there are only two pivot columns and pivot rows. The last row is all zeros, indicating that ${\bf A}$ is singular ($R=2<M=N=3$), i.e., $x_3$ is a free variable which can take any value. We have

\begin{displaymath}x_1+x_3=0,\;\;\;x_2+2x_3=0 \end{displaymath}

If we let $x_3=1$ , then we get $x_1=-1$, $x_2=-2$, and a special solution ${\bf x}_n=[-1,\;-2,\;1]^T$, which is in the nullspace $N({\bf A})$. However, the free variable $x_3$ can take any value $c$, the complete solution, i.e., the entire nullspace is

N({\bf A})=c {\bf x}_n=c\left[\begin{array}{r}-1 -2 1\end{array}\right]

Example 2:

Solve the following non-homogeneous equation

\begin{displaymath}{\bf A}{\bf x}=
\left[\begin{array}{ccc}1&2&5 2&3&8 3&1&5...
=\left[\begin{array}{c}19 31 22\end{array}\right]={\bf b}

We use Gauss-Jordan elimination to solve this system by applying a sequence of elementary row operations:

\begin{displaymath}[\begin{array}{c\vert c}{\bf A}&{\bf b}\end{array}]
...rray}{rrr\vert r}1&0&1&5 0&1&2&7 0&0&0&0\end{array}\right]

There are only two independent columns (or rows) in the rref form, i.e., the rank is $R=2<M=N=3$, indicating that ${\bf A}$ it is singular, and its inverse ${\bf A}^{-1}$ does not exist, we cannot convert ${\bf A}$ into an identity matrix ${\bf I}$. Instead we just have the following system with a coefficient matrix in the rref form, which can also be expressed in block matrix form:

\left[\begin{array}{rrr}1&0&1 0&1&2 0&0&0\end{array}\rig...
=\left[\begin{array}{c}{\bf b}_1 {\bf0}\end{array}\right]


{\bf I}=\left[\begin{array}{cc}1&0 0&1\end{array}\right],...
{\bf b}_1=\left[\begin{array}{c}5 7\end{array}\right]

Here ${\bf x}_{pivot}$ is a solution corresponding to the pivot columns and ${\bf x}_{free}$ represents free variables corresponding to the non-pivot columns, which are free variable that can take any value.

Solving for ${\bf x}_{pivot}$, we get

\begin{displaymath}{\bf I}{\bf x}_{pivot}+{\bf F}{\bf x}_{free}={\bf b}_1,\;\;\;...
+x_3\left[\begin{array}{c}-1 -2\end{array}\right]

If we let ${\bf x}_{free}=x_3=0$, we get a particular solution

\begin{displaymath}{\bf x}_{particular}=\left[\begin{array}{c}5 7 0\end{array}\right] \end{displaymath}

But as the free variable $x_3$ can take any value $c$, the complete solution is

{\bf x}_{complete}=\left[\begin{array}{c}5 7 0\end{array... x}_{particular}+c {\bf x}_n={\bf x}_{particular}+N({\bf A})

where ${\bf x}_n=[-1,\;-2,\;1]^T$ is the homogeneous solution for ${\bf A}{\bf x}={\bf0}$, which is in the 1-D nullspace $N({\bf A})=c\; {\bf x}_n$ already obtained in previous example. We therefore see that the complete solution of ${\bf A}{\bf x}={\bf b}$ is the entire nullspace $N({\bf A})$ translated by the particular solution ${\bf x}_{particular}$. For example, when $c=0,1,2$ we get the following solutions:

{\bf x}=\left[\begin{array}{c}5 7 0\end{array}\right],\...
{\bf x}=\left[\begin{array}{c}3 3 0\end{array}\right]

The following figure illustrates a 3-D $R^3$ space with a 2-D nullspace. The complete solution is the entire nullspace translated by a particular solution ${\bf x}_{particular}$.


Example 3: Consider the following linear equation system with an $M\times N$ coefficient matrix ${\bf A}$:

{\bf A}{\bf x}=\left[\begin{array}{rccc}1&2&3&4 4&3&2&1\\...
=\left[\begin{array}{r}3 2 4\end{array}\right] ={\bf b}

We find the complete solution of this system in the following steps:

If the right-hand side is ${\bf b}'=[1,\;3,\;5]^T$, then the row reduction of the augmented matrix yields:

\begin{displaymath}\left[\begin{array}{rrrr\vert r}1&2&3&4&1 4&3&2&1&3 -2&1&...
...vert r}1&2&3&4&1 0&1&2&3&0.2 0&0&0&0&1.2\end{array}\right]

The equation corresponding to the last row is $0=1.2$, indicating the system is not solvable (even though the coefficient matrix does not have full rank), as ${\bf b}'=[1,\;3,\;5]^T$ on the right-hand is not in the image, the column space $C({\bf A})$.

Example 4: Consider the linear equation system with coefficient matrix ${\bf A}^T$, the transpose of the coefficient matrix in the prevous example:

{\bf A}^T{\bf y}=\left[\begin{array}{rrr}1&4&-2 2&3&1 3&...
...eft[\begin{array}{c}3 11 19 27\end{array}\right]={\bf c}

If the right-hand side is ${\bf c}'=[1,\;1,\;2,\;3]^T$,

\left[\begin{array}{rrr\vert r}1&4&-2&1 2&3&1&1 3&2&4&2...
... r}1&4&-2&1 0&1&-1&1/5 0&0&0&1 0&0&0&2\end{array}\right]

indicating the system is not solvable, as this ${\bf c}'\notin C({\bf A}^T)$.

All four subspaces associated with this matrix ${\bf A}$ with $M=3$, $N=4$, and $R=2$ can be obtained in the last two examples:

  1. The row space $R({\bf A})=C({\bf A}^T)$ is an R-D subspace of $\mathbb{R}^4$, spanned by the first $R=2$ pivot rows of the rref of ${\bf A}$:

    \begin{displaymath}R({\bf A})=C({\bf A}^T)=
\left[\begin{array}{c}0 1 2 3\end{array}\right]\right) \end{displaymath}

  2. The nullspace $N({\bf A})$ is an (N-R)-D subspace of $\mathbb{R}^4$ spanned by the $N-R$ independent homogeneous solutions:

    \begin{displaymath}N({\bf A})=span\left(\left[\begin{array}{r}1 -2 1 0\end...
...left[\begin{array}{r}2 -3 0 1\end{array}\right] \right)

    Note that the basis vectors of $N({\bf A})$ are indeed orthogonal to those of $R({\bf A})$.
  3. The column space of ${\bf A}$ is the same as the row space of ${\bf A}^T$, which is the R-D subspace of $R^3$ spanned by the first two pivot rows of the rref of ${\bf A}^T$.

    \begin{displaymath}C({\bf A})=R({\bf A}^T)=span\left(\left[\begin{array}{c}1 0...
\left[\begin{array}{r}0 1 -1\end{array}\right]\right) \end{displaymath}

  4. The left nullspace $N({\bf A}^T)$ is a (M-R)-D subspace of $\mathbb{R}^3$ spanned by the homogeneous solutions (here one $3-2=1$ solution):

    \begin{displaymath}N({\bf A}^T)=span\left(\left[\begin{array}{r}-2 1 1\end{a...
=c\;\left[\begin{array}{r}-2 1 1\end{array}\right]

    Again note that the basis vectors of $N({\bf A}^T)$ are orthogonal to those of $C({\bf A})$.

In general, here are the ways to find the bases of the four subspaces:

Note that while the basis of $R({\bf A})$ can be obtained from the rref form of ${\bf A}$ as its rows are equivalent to those of ${\bf A}$, the basis of $C({\bf A})$ cannot be obtained as the columns of the rref form, as the columns of ${\bf A}$ have been changed by the row deduction operations and are not equivalent to the columns of the resulting rref form. But the basis of $C({\bf A})$ can be obtained from the rref form of ${\bf A}^T$, as its rows are equivalent to those of ${\bf A}^T$, which are the columns of ${\bf A}$.

We make the following observations:

All these results can be illustrated in the figure below, where we assume ${\bf x}_p\in R({\bf A})$ and ${\bf y}_p\in C({\bf A})$, which is not the case in these examples, but will be true when the systems were solved by the SVD method, discussed in the next section.


Here is a summary of the four subspaces associated with an $M$ by $N$ matrix ${\bf A}$ of rank $R$.

$M$, $N$, $R$ dim $R({\bf A})$ dim $N({\bf A})$ dim $C({\bf A})$ dim $R({\bf A}^T)$ solvability of ${\bf A}{\bf x}={\bf b}$
$M=N=R$ $R$ 0 $R$ 0 solvable, ${\bf x}={\bf A}^{-1}{\bf b}$ is unique solution
$M>N=R$ $R$ 0 $R$ $M-R$ over-constrained, solvable if ${\bf b}\in C({\bf A})$
$N>M=R$ $R$ $N-R$ $R$ 0 under-constrained, solvable, infinite solutions ${\bf x}={\bf x}_p+N({\bf A})$
$R<min(M,N)$ $R$ $N-R$ $R$ $M-R$ solvable only if ${\bf b}\in C({\bf A})$, infinite solutions

The following figure illustrates the case when $M=N=3$, and when ${\bf b}\notin C({\bf A})$. The system can only be approximately solved for the projection ${\bf p}\in C({\bf A})$ of ${\bf b}$in the column space. This is the optimal approximation in the least-squares sense as the error is minimized $\vert\vert{\bf e}\vert\vert\longrightarrow min$.


next up previous
Next: Solving Linear Systems by Up: Solving Linear Algebraic Equations Previous: LU Decomposition
Ruye Wang 2015-02-12