When we solve a linear system Ax = b for m×n
matrix A, its dimensions do not truelly describe the solution set. The
first step to understand this set is to show that the solution set for any
linear system is actually a vector space. Recall that ℝn
consists of all n-tuples that we represent as column vectors:
with some real numbers x1, x2,
... , xn. If one wants to deal with the field of complex
numbers, then we use ℂn that is similar to ℝn
with entries x1, x2,
... , xn taken as complex numbers. When matrix
Matrix A can be partitioned
according to its columns: \( {\bf A} = \left[ {\bf c}_1 \
{\bf c}_2 , \ \ldots , \ {\bf c}_n \right] , \) where
each column is an m-vector
The coefficients are the entries of x. So applying A to all
possible n-column vectors x, we obtain all possible linear
combinations of columns of matrix A. Such set is a span of all columns
of matrix A and it is a vector space embedded into ℝn
or ℂn depending what scalars are used.
Recall that a set of vectors β is said to generate or span a
vector space V if every element from V can be represented as a
linear combination of vectors from β.
The range (also called the column space or image) of a m × n matrix A is the span (set of all possible linear combinations) of its column vectors. The column space of a matrix is the image or range of the corresponding matrix transformation. We will denote it as Range(A). So it is a
subspace of ℝm in case of real entries or ℂm
when matrix A has complex entries.
Note that we have several alternatives to label the same object---range in our
case. This is usually the case when two topics (matrix theory and vector
spaces and their transformations) overlap,
The dimension of the column space is called the column rank of matrix A. This corresponds to the maximal number of linearly independent columns of A. A matrix is said to have full column rank if its columns are linearly independent.
Since \( {\bf x}^{\mathrm T} {\bf A}^{\mathrm T} =
\left( {\bf A}\, {\bf x} \right)^{\mathrm T} , \)
the column space of a matrtix A equals the row space of
its transpose matrix AT
(or, in general, its adjoint \( {\bf A}^{\ast} = \overline{\bf A}^{\mathrm T} \) ), so a basis can be computed by reducing
AT to row-echelon form. However, this is not the best way.
Those combinations fill up a plane in ℝ3. If the right side
b lies on that plane, then it is one of the combinations and
x = (x1, x2) is a solution to
Ax = b. If b is not in the column space, then there is no
solution to our 3 equations in 2 unknowns.
Theorem:
The system Ax = b is conistent if and only if b is in
the range of A.
When b is in the range of A, it is a combination of the columns.
The coefficients in that combination give us a solution x to the system
Ax = b.
When the above linear system is consistent, then coefficients of x are
exactly coefficients in the linear combination for b expressed as via
columns of A.
Our next very important question is how to determine the dimension of the
range. It is equal to the number of linearly independent column vectors in
matrix A. In other words, we need to determine the column rank of a
rectangualr matrix.
Recall that the dimension of a vector space V is the cardinality
(i.e. the number of vectors) of a basis of V over its set of scalars.
A common approach to finding a basis of the column space of a matrix is to
reduce it to a simpler form, generally row echelon form, by elementary row operations. Row operations do not change the row space (hence do not change the row rank). Mathematica has no build-in command to determine a row echelon form, but it has RowReduce command to determine the (unique for each matrix) reduced row echelon form or Gauss-Jordan form. From computational point of view, rref is more expensive than just row echelon form (ref for short). However, for theoretical purpose, we will use Gauss--Jordan form. Generally speaking, we cannot utilize rref or ref for column space because elementary row operations may change column vectors. Hence, we need to use elementary column operations to preserve the column space. These operations are equivalent to multiplication from right by elementary matrices. So far, they were not in use because we focus on solving linear system of equations, for which elementary column operations are not suitable.
Example: Let us pick up a 4×4 matrix with
random integer entries:
Note that when you execute the above Mathematica command, you most
likely will get different random matrix. As usual, we choose the first pivot
as the entry "9" in the upper left coner. Your software will also pick the same
pivot because it is the largest entry in the first column. To eliminate
entries to the right of the pivot, we multiply the random matrix by the
elementary matrix from the right:
Since the chosen matrix is invertible, the set of columns in it provides a
basis for the range of the matrix. Therefore, the range is ℝ4.
If we consider another matrix
form the basis for the column space. Actually, the first three columns in the
original matrix B can be also chosen as basis vectors because pivots
belong to these columns.
■
then B results from A by the row operation: R2
→R2 - 2 R1. However, these two
matrices have different column spaces because
\[
Column\left({\bf A}\right) = \left\{ \begin{bmatrix} k \\ -2\,k \end{bmatrix}
\, : \ k \in \mathbb{R} \right\} , \qquad Column\left({\bf B}\right) =
\left\{ \begin{bmatrix} k \\ 0 \end{bmatrix} \, : \ k \in \mathbb{R} \right\} .
\qquad \blacksquare
\]
There is nothing special in multiplication by elementary matrices (from left
or right---they could be of different dimensions). What is important in these
matrices is that they are invertible. Actually, every nonsigular matrix is a
product of elementary matrices. It turns out that multiplication by an
arbitrary invertible matrix does not change neither row rank nor column rank
because to each such operation corresponds an isomorphism or a linear bijection. Recall that an isomorphism
between two vector spacesV and U is a
one-to-one and onto correspondence; this means that there exists a linear map
T : V ↦ U such that its inverse
T-1 also exists. When V and U are
finite dimensional and corresponding ordered bases are established in each
space, any
linear transformation is equivalent to a multiplication by an invertible
square matrix and vice versa. An isomorphism cannot change the dimention of a
space, so it exists only between vector spaces of the same dimensions.
Therefore, we come to conclusion that the rank is clearly the same for both
row rank and column rank, and equals the number of pivots (or basic columns)
and also the number of non-zero rows.
Theorem:
Let A be an m×n matrix, so it can be considered as
a transformation from ℝn into ℝm. If
β = { v1, v2, ...,
vn } is a basis for ℝn, then its range
(the column space) is spanned on vectors Aβ =
{ Av1, Av2, ...,
Avn }.
Clearly, Avi belongs to the column space for each
i. Since the range is a subspace of ℝn, it contains
Theorem (Colomn space basic theorem):
When Gaussian elimination procedure is applied to an m×n
real matrix A, its pivot columns form a basis for the column space
(range) of matrix A. ▣
Although row reduction is enough to identify pivots, we will use Gauss-Jordan
form for simplicity. Let R be the reduced row echelon form of an
m×n real matrix A. Suppose that R has
r pivots. We extract the corresponding columns containing pivots from
matrix A to form the m×r matrix
Ar; simlarly, we build the m×r matrix
from pivot columns of R and denote it by Rr.
Obviously, the latter is a full column rank matrix because every column has
the only one nonzero entry, which is a "1," situated at different places
because they identify the location of pivots. We need to show that matrix
Ar has linearly independent columns. Using its partition, we
represent Ar as vector of columns:
where x is a column vector of length r. Since the linear vector
equation \( {\bf A}_r {\bf x} = {\bf 0}_m \) has
exactly the same set of solutions, which is vector x, as
\( {\bf R}_r {\bf x} = {\bf 0}_m , \) we conclude
that all entries of x are zeroes. Hence column vectors in matrix
Ar are linearly independent, and the column rank is at least
r.
To finish the proof, we need to show that if we append any other column to
Ar, the resulting matrix will contain linearly dependent
column vectors. So we form the linear combination of these vectors and equan
it to zero
where \( \left[ {\bf A}_r \big\vert {\bf v} \right] \) is the augmented matrix formed from Ar by appending extra
column vector v from A not containing pivot. Applying elementary
row operations (that we know do not change the solution set) to this augmented
matrix, we reduce it to gauss-Jordan form:
where u is a column vector in the reduced row echelon form not
containing a pivot. This vector u appears in matrix R somewhere
to the right of a pivot vector p that has the same number of zeroes.
Therefore, vector u is a linear combination of all pivot vectors in
matrix R that are situated to the left of u. Since the solution
set of two systems of equations
We first find the 6×4 matrix A that represents T as a
multiplication. The image of T is the subspace of ℝ6
spanned by the columns of matrix A. We will find a basis for the range
of T by applying RowReduction to the transposed matrix to
A and taking its nonzero rows.
T[x_, y_, z_, w_] := {2 x + 6 y + z - w, 3 x - 17 y + 3 z - w,
x + 7 y + 5 z + 3 w, 2 x + 26 y + 3 z + w, x - 3 y + 4 z + 2 w,
x + 29 y - z - w}
(A = Transpose[{T[1, 0, 0, 0], T[0, 1, 0, 0], T[0, 0, 1, 0],
T[0, 0, 0, 1]}]) // MatrixForm
Now we apply RowReduce command (which is Mathematica's version
of rref) to the transposed matrix to obtain the basis of the range,
written as row vectors:
From the matrix ImT above, we see that the subspace Im(T) has
dimension three, with the first three rows of the matrix ImT as a
basis. Thus, any vector in Im(T) can be expressed as alinear
combination of the three vectors:
