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

## Fundamental theorem of linear algebra

An M by N matrix can be expressed in terms of either its M-D column vectors or its N-D row vectors :

where and are respectively the ith row vector and jth column vector (note that through out the text, all vectors are assumed to be vertical):

The by matrix in the linear function (a transformation) maps an N-D vector in the domain of the function, , to an M-D vector in the codomain of the function, .

The fundamental theorem of linear algebra concerns the following four fundamental subspaces associated with any matrix with rank , there are independent columns and rows.

• The column space of is a space spanned by its M-D column vectors ( of which are independent):

which is an R-D subspace of composed of all possible linear combinations of its column vectors:

The column space is the image (or range) of the linear transformation from to . The equation system is solvable if and only if . The dimension of the column space is the rank of , .

• The row space of is a space spanned by its N-D row vectors ( of which are independent):

which is an R-D subspace of composed of all possible linear combinations of its row vectors:

As the rows and columns in are respectively the columns and rows in , the row space of is the column space of , and the column space of is the row space of :

The number of linearly independent row vectors is the dimension of the row space , which is the rank , i.e.,

• The nullspace (kernel) of , denoted by , is the set of all vectors that satisfy the homogeneous equation

i.e.,

In particular, when , we get , i.e., the origin must be in the nullspace.

As all are orthogonal to , is orthogonal to the row space :

The dimension of the nullspace is called the nullity of : . Also, according to the rank-nullity theorem,

we see that and are mutually exclusive and complementary:

They are orthogonal complement of each other, denoted by

• The nullspace of (also called left nullspace of , denoted by , is the set of all vectors that satisfy the homogeneous equation

i.e.,

As all are orthogonal to , is orthogonal to the column space :

Also, for and we have

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

Example 0:

By elementary row operations, we can convert into the rref form:

We see that . Alternatively, if we define another matrix by switching the 2nd and 3rd columns of , we have

Now we have . We see that in either case, the column space is a 2-D plane spanned by any two of the three column vectors.

The columns in the rref matrix that contain a single 1, called a pivot element, are the pivot columns, and the corresponding rows each containing a pivot are the pivot rows, which span the R-D row space . However, the columns of are changed by the row reduction operations and the pivot columns of the rref form do not span the column space .

The number of pivots in the rref form is the rank of , the number of independent rows or columns in , i.e., the dimension of both and :

The pivot rows correspond to the independent equations in the system , while the remaining non-pivot rows containing all zeros are not independent. They don't play any role in the equation system , as they map any to .

Example 1:

Solve the following homogeneous equation

Applying the elementary row operations, we get

In this rref form, there are only two pivot columns and pivot rows. The last row is all zeros, indicating that is singular (), i.e., is a free variable which can take any value. We have

If we let , then we get , , and a special solution , which is in the nullspace . However, the free variable can take any value , the complete solution, i.e., the entire nullspace is

Example 2:

Solve the following non-homogeneous equation

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

There are only two independent columns (or rows) in the rref form, i.e., the rank is , indicating that it is singular, and its inverse does not exist, we cannot convert into an identity matrix . Instead we just have the following system with a coefficient matrix in the rref form, which can also be expressed in block matrix form:

where

Here is a solution corresponding to the pivot columns and represents free variables corresponding to the non-pivot columns, which are free variable that can take any value.

Solving for , we get

If we let , we get a particular solution

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

where is the homogeneous solution for , which is in the 1-D nullspace already obtained in previous example. We therefore see that the complete solution of is the entire nullspace translated by the particular solution . For example, when we get the following solutions:

The following figure illustrates a 3-D space with a 2-D nullspace. The complete solution is the entire nullspace translated by a particular solution .

Example 3: Consider the following linear equation system with an coefficient matrix :

We find the complete solution of this system in the following steps:
• Construct the augmented matrix and then convert it to the rref form:

As there are two pivot rows in the rref, we know . The equation system now takes this block matrix form:

where

Multiplying out we get

• Find the homogeneous solution for equation by setting :

We use the two standard basis vectors and of the nullspace and get

• Find the particular solution of the non-homogeneous equation by setting

• Get the complete solution:

If the right-hand side is , then the row reduction of the augmented matrix yields:

The equation corresponding to the last row is , indicating the system is not solvable (even though the coefficient matrix does not have full rank), as on the right-hand is not in the image, the column space .

Example 4: Consider the linear equation system with coefficient matrix , the transpose of the coefficient matrix in the prevous example:

• Carrying out elementary row operations to the augmented matrix we get

The original system can now be written as

where

Multiplying out we get

• Find the homogeneous solution for , by setting . Assuming the free variable , We get

• Find the particular solution of by assuming :

• Get the complete solution:

If the right-hand side is ,

indicating the system is not solvable, as this .

All four subspaces associated with this matrix with , , and can be obtained in the last two examples:

1. The row space is an R-D subspace of , spanned by the first pivot rows of the rref of :

2. The nullspace is an (N-R)-D subspace of spanned by the independent homogeneous solutions:

Note that the basis vectors of are indeed orthogonal to those of .
3. The column space of is the same as the row space of , which is the R-D subspace of spanned by the first two pivot rows of the rref of .

4. The left nullspace is a (M-R)-D subspace of spanned by the homogeneous solutions (here one solution):

Again note that the basis vectors of are orthogonal to those of .

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

• The basis vectors of are the pivot rows of the rref form of .
• The basis vectors of are the pivot rows of the rref form of .
• To find the basis for , reduce to the rref form, identify all free variables corresponding to non-pivot columns, set one of them to 1 and all others to 0, solve homogeneous system to find the pivot variables to get one basis vector. Repeat the process for each of the free variables to get all basis vectors.
• By doing the same as above for , we get the basis for .

Note that while the basis of can be obtained from the rref form of as its rows are equivalent to those of , the basis of cannot be obtained as the columns of the rref form, as the columns of have been changed by the row deduction operations and are not equivalent to the columns of the resulting rref form. But the basis of can be obtained from the rref form of , as its rows are equivalent to those of , which are the columns of .

We make the following observations:

• The basis vectors of each of the four spaces are independent, the basis vectors of and are orthogonal, and . Similarly, the basis vectors of and are orthogonal, and . In other words, the four subspaces indeed satisfy the following orthogonal and complementary properties:

i.e., they are orthogonal complements: .

• For to be solvable, the constant vector on the right-hand side must be in the column space, i.e., . Otherwise the equation is not solvable, even when . Similarly, for to be solvable, must be in the row space . In the examples above, both and are indeed in their corresponding column spaces:

But as and , the corresponding systems have no solutions.

• All homogeneous solutions of are in the nullspace , but in general the particular solutions are not necessarily in the row space . In the example above, is a linear combination of the basis vectors of and basis vectors of :

where

are the projections of onto and , respectively, and is another particular solution without any homogeneous component that satisfies , while is a homogeneous soluton satisfying .

• All homogeneous solutions of are in the left nullspace , but in general the particular solutions . are not necessarily in the column space. In the example above, is a linear combination of the basis vectors of and basis vector of :

where is a particular solution (without any homogeneous component) that satisfies .

All these results can be illustrated in the figure below, where we assume and , 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 by matrix of rank .

 , , dim dim dim dim solvability of 0 0 solvable, is unique solution 0 over-constrained, solvable if 0 under-constrained, solvable, infinite solutions solvable only if , infinite solutions

The following figure illustrates the case when , and when . The system can only be approximately solved for the projection of in the column space. This is the optimal approximation in the least-squares sense as the error is minimized .

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