Matrices, Bases, Rank, Nullity, Dimension

Matrices

A n\times m matrix over \mathbf{R} is an array of elements of \mathbf{R} with n rows and m columns. The set of such is denoted M_{n\times m}(\mathbf{R}). Complex arrays make up M_{n\times m}(\mathbf{C}).

The set M_{n\times m}(\mathbf{R}) (or \mathbf{C}) is a real (complex) vector space of dimension nm (“unwrap the matrices”). Addition and scalar multiplication are done entry by entry.

So if A=(a_{ij}) and B=(b_{ij}) with 1\le i\le n and 1\le j\le m then A+B has entries (a_{ij}+b_{ij}) and \lambda A has entries (\lambda a_{ij}) for \lambda\in \mathbf{R} or \mathbf{C}.

Elements of \mathbf{R}^{n} can be represented as n\times 1 matrices (column vectors) or 1\times n matrices (row vectors).

Unless we make an explicit remark otherwise, we will view \mathbf{R}^{n} as the space of n\times 1 real column vectors (same for \mathbf{C}).

Matrix Multiplication

Matrix multiplication is defined for a pair A,B if the number of columns of A equals the number of rows of B. The product has the same number of rows as A and the same number of columns as B. Specifically:

If A=(a_{ij}) is n\times m and B=(b_{ij}) is m\times k then C=AB has entries (c_{ij}) where c_{ij} = \sum_{r=1}^{m} a_{ir}b_{rj} for 1\le i\le n and 1\le j\le k.

Matrix multiplication is associative (AB)C=A(BC) and distributes over addition (A+B)C=AC+BC and A(B+C)=AB+AC but is not commutative. Even if both AB and BA are defined, they are typically not equal.

Linear Maps

A function from L:\mathbf{R}^{m}\to\mathbf{R}^{n} is linear if L(x+y)=L(x)+L(y) and L(ax)=aL(x).

Let A be an n\times m matrix. The function L_{A}(x)=Ax is a function from \mathbf{R}^{m} (viewed as column vectors) to \mathbf{R}^{n}.

If A is an n\times m matrix and B is a k\times n matrix then L_{A}:\mathbf{R}^{m}\to \mathbf{R}^{n} and L_{B}:\mathbf{R}^{n}\to \mathbf{R}^{k}.

The composed map L_{B}\circ L_{A} goes from \mathbf{R}^{n} to \mathbf{R}^{m} to \mathbf{R}^{k}.

From the associativity of matrix multiplication we have L_{B}\circ L_{A}=L_{BA} since B(Ax)=(BA)x.

Everything above holds with \mathbf{R} replaced by \mathbf{C}.

Key subspaces and invariants

Given a matrix A there are a collection of important spaces and numerical invariants that describe the linear map L_{A} associated to A.

Definition: The column space of A\in M_{n\times m}(\mathbf{R}) is the subspace of \mathbf{R}^{n} spanned by the columns of A.

The column space of A is the same as the image of the linear map L_{A} inside \mathbf{R}^{n}.

This is because if x\in R^{m}, then one way to interpret the product Ax is as: Ax = \sum A_{.i}x_{i}

where A_{.i} is the ith column of A and x_{i} is the ith entry of x. Thus the image of L_{A} is the subspace obtained by taking all linear combinations of columns of A, which is the column space.

Definition: The column rank of A is the dimension of the column space of A.

Nullspace (or kernel) and nullity

The nullspace or kernel of A is the subspace of x\in\mathbf{R}^{m} such that Ax=0. This is a subspace since, if x and y satisfy Ax=Ay=0, then A(x+y)=0; and if A(x)=0 then A(cx)=cA(x)=0.

The nullity of A is the dimension of the nullspace of A.

Row space

The row space of A is the subspace of \mathbf{R}^{m} spanned by the rows of A.

The row rank of A is the dimension of the row space.

Row and Column Operations and Elementary Matrices

The following three types of operations on matrices are called “elementary row operations”:

Swap two rows of A.
Multiply a row of A by a scalar.
Let A_{j.} be the j^{th} row of A and let \lambda be a scalar. Given i and j, replace A_{j.} by A_{j.}-\lambda A_{i.}

Associated with each such operation is a square matrix E called an elementary matrix:

Swapping row i and row j corresponds to the matrix which has a 1 in position i,j and j,i, 1’s on the diagonal in positions other than i,j; and zeros elsewhere.
Multiplying row i by \lambda corresponds to the matrix which has 1 on the diagonal in every position except i, where it has \lambda; and zeros elsewhere.
The third operation has 1’s on the diagonal, together with -\lambda in position row j, column i.

P_{ij}= \left(\begin{smallmatrix} \ddots & & & \\ & 0 & 1 & \\ & 1 & 0 & \\ & & & \ddots \end{smallmatrix}\right) \quad D_i(\lambda)= \left(\begin{smallmatrix} \ddots & & \\ & \lambda & \\ & & \ddots \end{smallmatrix}\right) \quad R_{ji}(\lambda)= \left(\begin{smallmatrix} \ddots & & & & \\ & 1 & & & \\ & & \ddots & & \\ & -\lambda & & 1 & \\ & & & & \ddots \end{smallmatrix}\right)

Constructing A' from A by an elementary row operation is the same as multiplying A by the corresponding elementary matrix E, so A'=EA.

The elementary matrices are invertible in the sense that, for each E, there is a matrix F so that FE=EF=I where I is the matrix with ones on the diagonal and zeros elsewhere. This is because the elementary row operations themselves can be “undone” by other elementary row operations.

A swap is undone by a the same swap again.
Multiplying a row by \lambda is undone by multiplying by 1/\lambda.
Undoing A_{j.}\to A_{j.}-\lambda A_{i.} is undone by A_{j.}\to A_{j.}+\lambda A_{i.}.

Proposition: If A' is obtained from A by a sequence of elementary row operations, then:

The row space of A' is the same as that of A.
The nullspace of A' is the same as that of A.
The column rank of A' is the same as that of A (although the column space itself may be different).

To see this, first notice that the first two elementary row operations clearly don’t change the subspace spanned by the rows. For the third one, since A_{j.} is in the span of A_{1.},\ldots, A_{j.}-\lambda A_{i.},\ldots, A_{n.}, the third operation also doesn’t affect the span of the rows.

For the nullspace, suppose x is in the nullspace of A. Then A'x=EAx=E(Ax)=0 so x is in the nullspace of A'. Conversely, if x is in the nullspace of A', then since A'=EA, we have 0=A'x=EAx. But there is a matrix F with FE=I, so 0=FEAx=IAx=Ax and x is in the nullspace of A.

Now let e_1,\ldots, e_k be a basis for the column space of A and suppose A'=EA. We claim Ee_1,\ldots, Ee_k is a basis for the column space of A'. To see this suppose x is in the column space of A'. Then x=EAy for some y. Since Ay is in the column space of A, it is a linear combination of the e_{i} and so x is a linear combination of the Ee_{i}. This proves the Ee_{i} span the column space of A'. Now suppose \sum a_{i}Ee_{i}=0. Then E(\sum a_{i}e_{i})=0. Multiplying by F gives \sum a_{i}e_{i}=0 and thus all a_{i}=0.

Thus the column rank of A and A' are the same.

Row Reduction and Computation

A matrix is in row reduced echelon form if the following conditions hold:

The first nonzero entry in each row is 1. These entries are called “pivots”.
These pivots move “down and to the right”. So if row i has its first nonzero entry in column j, then row i+1 has its first nonzero entry in a column strictly greater than j.
A pivot is the only nonzero entry in its column.

A generic matrix in row reduced echelon form looks like this, where * denotes an arbitrary entry:

\begin{pmatrix} \boxed{1} & * & 0 & * & 0 & * \\ 0 & 0 & \boxed{1} & * & 0 & * \\ 0 & 0 & 0 & 0 & \boxed{1} & * \\ 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}

Here the pivots (boxed 1’s) occur in columns 1,3,5, moving down and to the right; the pivot columns are otherwise all zero; the non-pivot columns (2,4,6) may contain arbitrary entries above the next pivot; and any all-zero rows sink to the bottom.

Proposition: Given an n\times m matrix A, there is a sequence of row operations that transforms A into a matrix A' in row reduced, echelon form.

Proposition: If A is in row reduced, echelon form then:

The row (and column) ranks r are the equal to the number of pivots. To see this, first observe that every row is either all zero or a pivot row, so the row space is spanned by the pivot rows and these are independent. Then observe that the pivot columns are independent, and any non-pivot column can be written as a linear combination of the pivot columns.
The nullity is equal to m-r. For each non-pivot column j, define a vector x^{(j)}\in\mathbf{R}^m by x^{(j)}_k= \begin{cases} 1 & k=j\\ 0 & k \text{ a non-pivot column}, k\neq j\\ -A_{i,j} & k=p_i, \text{ the pivot column of row } i. \end{cases} Since the pivot in row i is the only nonzero entry in column p_i, row i of Ax^{(j)} is just A_{i,p_i}x^{(j)}_{p_i}+A_{i,j}x^{(j)}_j=-A_{i,j}+A_{i,j}=0; the all-zero rows of A contribute nothing. So x^{(j)}\in\ker A.

For example, filling in numbers for the *’s in the generic matrix above, A= \begin{pmatrix} 1 & 2 & 0 & 3 & 0 & -1\\ 0 & 0 & 1 & 4 & 0 & 5\\ 0 & 0 & 0 & 0 & 1 & 6\\ 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}, the pivot columns are 1,3,5 and the non-pivot columns are 2,4,6. Taking j=6, the recipe puts a 1 in position 6, 0’s in positions 2,4, and -A_{i,6} in position p_i for each pivot row i: x^{(6)}= \begin{pmatrix}-A_{1,6}\\ 0\\ -A_{2,6}\\ 0\\ -A_{3,6}\\ 1\end{pmatrix} = \begin{pmatrix}1\\ 0\\ -5\\ 0\\ -6\\ 1\end{pmatrix}. Directly multiplying out confirms Ax^{(6)}=0.

These vectors are independent: restricted to the non-pivot coordinates, x^{(j)} is just the j-th standard basis vector, so different j’s give visibly independent vectors.

They also span \ker A: given any x\in\ker A, set y=\sum_{j \text{ non-pivot}} x_j\, x^{(j)}. By construction y agrees with x on every non-pivot coordinate, so x-y\in\ker A and x-y vanishes on all non-pivot coordinates. But then row i of A(x-y)=0 reads (x-y)_{p_i}=0 as well, so x-y=0, i.e. x=y.

So the x^{(j)}, one for each of the m-r non-pivot columns, form a basis of \ker A.

Corollary: For any matrix A, we have:

The row and column ranks of A agree; this number is called the rank of A.
\mathrm{rank}(A)+\mathrm{nullity}(A)=m where m is the number of columns of A.

Back to dimension

Earlier we claimed that all bases of a finite dimensional vector space have the same number of elements. Now we can complete the proof of that.

Suppose X=\{e_1,\ldots, e_n\} is a spanning set and Y=\{f_1,\ldots, f_{m}\} is a linearly independent set.

Since X spans, we can write, for all 1\le i\le n and 1\le j\le m: f_{i} = \sum_{j} a_{ij} e_{j} for scalars a_{ij}. This gives an m\times n matrix A=(a_{ij}).

Suppose we have a relation among the rows of A, so that there are b_{i}, not all zero, with \sum_{i} b_{i}a_{ij}=0 for all j.

This would mean that \sum_{i}b_{i}f_{i}=\sum_{i}b_{i}\sum_{j}a_{ij}e_{j}=0

which contradicts the independence of Y. So the rank of A is at least m.

It follows that the number of columns of A, which is |X|, is at least m. So |X|\ge |Y|.

As a result, if X and Y are both bases, hence both spanning and linearly independent, then |X|\ge|Y| and |Y|\ge |X| so they have the same number of elements.

Algorithms

The algorithm yielding the rref form gives an explicit way to compute the nullity of a matrix.

To determine if a vector v is in the range of the matrix A we want to determine if there is an x so that Ax=v.

Make the “augmented matrix” A'=[A,v] by adding v as a column to A. Put it in rref form.

If the last column has a pivot, then v is not in the range. If it doesn’t, then it is in the range. Essentially, you are deciding if the vector v is linearly dependent on the columns of A, which is the same as asking if it is in the range (or column space) of A.