Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Matrix product and rank

by , PhD

This lecture discusses some facts about matrix products and their rank. In particular, we analyze under what conditions the rank of the matrices being multiplied is preserved.

Table of Contents

Bound on the rank of a product

The next proposition provides a bound on the rank of a product of two matrices.

Proposition Let A be a $K imes L$ matrix and $B$ an $L imes M$ matrix. Then,[eq1]

Proof

The space spanned by the columns of $AB$ is the space $S$ of all vectors $s$ that can be written as linear combinations of the columns of $AB$:[eq2]where $v$ is the $M imes 1$ vector of coefficients of the linear combination. We can also write[eq3]where $Bv$ is an $L imes 1$ vector (being a product of an $L imes M$ matrix and an $M imes 1$ vector). Thus, any vector $sin S$ can be written as a linear combination of the columns of A, with coefficients taken from the vector $Bv$. As a consequence, the space $S$ is no larger than the span of the columns of A, whose dimension is [eq4]. This implies that the dimension of $S$ is less than or equal to [eq5]. Since the dimension of $S$ is the rank of $AB$, we have[eq6]Now, the space spanned by the rows of $AB$ is the space $T$ of all vectors $t $ that can be written as linear combinations of the rows of $AB$:[eq7]where $u$ is the $1 imes K$ vector of coefficients of the linear combination. We can also write[eq8]where $uA$ is a $1 imes L$ vector (being a product of a $1 imes K$ vector and a $K imes L$ matrix). Thus, any vector $tin T$ can be written as a linear combination of the rows of $B$, with coefficients taken from the vector $uA$. As a consequence, the space $T$ is no larger than the span of the rows of $B$, whose dimension is [eq9]. This implies that the dimension of $T$ is less than or equal to [eq10]. Since the dimension of $T$ is the rank of $AB$, we have[eq11]The two inequalities[eq12]are satisfied if and only if[eq13]

Multiplication by a full-rank square matrix preserves rank

Another important fact is that the rank of a matrix does not change when we multiply it by a full-rank matrix.

Proposition Let A be a $K imes L$ matrix and $B$ a square $L imes L$ matrix. If $B$ is full-rank, then[eq14]

Proof

Remember that the rank of a matrix is the dimension of the linear space spanned by its columns (or rows). We are going to prove that the ranks of A and $AB$ are equal because the spaces generated by their columns coincide. Denote by $S$ the space generated by the columns of A. Any vector $sin S$ can be written as a linear combination of the columns of A:[eq15]where $v$ is the $L imes 1$ vector of coefficients of the linear combination. Since $B$ is full-rank and square, it has $L$ linearly independent columns that span the space of all $L imes 1$ vectors (they are equivalent to the canonical basis). Therefore, there exists an $L imes 1$ vector $u$ such that[eq16]Thus[eq17]We have just proved that any vector $sin S$ can be written as a linear combination of the columns of $AB$. Furthermore, the columns of $AB$ do not generate any vector $s otin S$. To see this, note that for any vector of coefficients $u$, if [eq18]then[eq19]so that $sin S$. Thus, we have proved that the space spanned by the columns of A and that spanned by the columns of $AB$ coincide. As a consequence, also their dimensions (which by definition are equal to the ranks of A and $B$) coincide.

Proposition Let A be a $K imes L$ matrix and $B$ a square $K imes K$ matrix. If $B$ is full-rank, then[eq20]

Proof

The proof of this proposition is almost identical to that of the previous proposition. It is left as an exercise (see the exercise below with its solution).

The product of two full-rank square matrices is full-rank

An immediate corollary of the previous two propositions is that the product of two full-rank square matrices is full-rank.

Proposition Let A and $B$ be two $K imes K$ full-rank matrices. Then, their products $AB$ and $BA$ are full-rank.

Proof

Being full-rank, both matrices have rank K. Therefore, by the previous two propositions[eq21]But $AB$ and $BA$ are $K imes K$, so they are full-rank.

Gram matrices

We now present a very useful result concerning the product of a non-square matrix and its transpose.

Proposition Let A be a $K imes L$ full-rank matrix with $Kgeq L$. Then, the product $A^{ op }A$ is full-rank.

Proof

Let $S$ be the space of all $L imes 1$ vectors. Suppose that there exists a non-zero vector $sin S$ such that[eq22]Then,[eq23]or[eq24]or[eq25]where [eq26] denotes the k-th entry of the Kx1 column vector $As$. This is possible only if [eq27]for $k=1,ldots ,K$, that is, only if[eq28]which is impossible because A is full-rank, it has less columns than rows and, hence, its columns are linearly independent. Thus, the only vector that gives[eq29]is $s=0$, which implies that the columns of $A^{ op }A$ are linearly independent and $A^{ op }A$ is full-rank.

The matrix $A^{ op }A$ is called a Gram matrix.

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Let A be a $K imes L$ matrix and $B$ a full-rank $K imes K$ matrix. Prove that if $B$ is full-rank, then[eq30]

Solution

Keep in mind that the rank of a matrix is the dimension of the space generated by its rows. We are going to prove that the spaces generated by the rows of A and $BA$ coincide, so that they trivially have the same dimension, and the ranks of the two matrices are equal. Denote by $S$ the space spanned by the rows of A. Any $sin S$ is a linear combination of the rows of A:[eq31]where $v$ is the $1 imes K$ vector of coefficients of the linear combination. Since $B$ is full-rank, it has K linearly independent rows that span the space of all $1 imes K$ vectors. As a consequence, there exists a $1 imes K$ vector $u$ such that[eq32]Thus[eq33]This means that any $sin S$ is a linear combination of the rows of $BA$. Moreover, the rows of $BA$ do not generate any vector $s otin S$: for any vector of coefficients $u$, if [eq34]then[eq35]so that $sin S$. Thus, the space spanned by the rows of A and that spanned by the rows of $AB$ coincide. As a consequence, also their dimensions coincide.

How to cite

Please cite as:

Taboga, Marco (2021). "Matrix product and rank", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/matrix-product-and-rank.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.