Matrices

With matrices being a representation of linear maps, we can study their properties leveraging that.

Definition. Let $B$ be a $m \times r$ matrix and $C$ be a $r \times n$ matrix. Then their product $A = BC$ is a $m \times n$ matrix such that

\[A_{ij} = \sum_{k=1}^{r} B_{ik} C_{kj}\]

We have seen that this matches the properties of composite of linear maps. But on the other hand, if we consider each column of $A$ as a vector $A^{(j)} \in \mathbb{F}^m$ then by the multiplication formula, we have

\[A^{(j)} = C_{1j} B^{(1)} + C_{2j} B^{(2)} + ... + C_{rj} B^{(r)} = B C^{(j)}\]

The first expansion means $A^{(j)}$ are linear combinations of column vectors of $B$ with $C_{kj}$ as coefficients. The second expansion means $A^{(j)}$ are the image of $C^{(j)}$ under the linear map $B$.

Proposition. Let $A$ be an $n \times n$ matrix over $\mathbb{F}$. The following are equivalent

  • there exists a matrix $B$ such that $BA = I_n$;

  • there exists a matrix $C$ such that $AC = I_n$.

Moreover, if both holds then $B = C$ and we write $A^{-1} = B = C$ and $A$ is invertible.

Proof.

Let $\alpha, \beta, \gamma, \iota: \mathbb{F}^n \to \mathbb{F}^n$ be the linear maps represented by $A, B, C$ and $I_n$ with respect to the standard basis.

$BA = I_n$ iff there exists $\beta$ such that $\beta \alpha = \iota$, which it implies $\alpha$ is injective and therefore an isomorphism. Conversely, if $\alpha$ is an isomorphism then there exists $\beta$ such that $\beta \alpha = \iota$ by definition. Therefore, $BA = I_n$ iff $\alpha$ is an isomorphism.

$AC = I_n$ iff there exists $\gamma$ such that $\alpha \gamma = \iota$, which implies $\alpha$ is surjective and therefore an isomorphism. Similarily, $AC = I_n$ iff $\alpha$ is an isomorphism.

If $\alpha$ is an isomorphism, then $\beta$ and $\gamma$ must both be the set-theoretic inverse of $\alpha$ and so $B = C$.

Change of Basis

Proposition. Suppose that $(e_1, …, e_m)$ and $(u_1, …, u_n)$ are two bases for $U$ over $\mathbb{F}$ and $(f_1, …, f_m)$ and $(v_1, …, v_n)$ are two bases for $V$. Let $\alpha: U \to V$ be a linaer map, $A$ be the matrix representation with respect to $(e_i)$ and $(f_j)$ and $B$ be that with respect to $(u_i)$ and $(v_j)$. Then

\[B = Q^{-1}AP\]

where

\[u_i = \sum P_{ki} e_k \qquad \text{and} \qquad $v_j = \sum Q_{lj} f_l\]

in which $P$ can be viewed as the matrix representing the identity map from $U$ with basis $(u_i)$ to $U$ with basis $(e_i)$ and $Q$ as that of the identity map from $V$ with basis $(v_j)$ to $(f_j)$.

Proof.

By defintion,

\[\alpha(u_i) = \sum_j B_{ji} v_j = \sum_{j,l} B_{ji} Q_{lj} f_l = \sum_l (QB)_{li} f_l\]

On the other hand,

\[\alpha(u_i) = \alpha \left( \sum_k P_{ki} e_k \right) = \sum_{k,l} P_{ki} A_{lk} f_l = \sum_l (AP)_{li} f_l\]

Hence, $QB = AP$. Since $Q$ is invertible, $B = Q^{-1}AP$.

Definition. Two matrices $A, B \in \text{Mat}_{n,m}(\mathbb{F})$ are equivalent if there are invertible matrices $P \in \text{Mat}_m(\mathbb{F})$ and $Q \in \text{Mat}_n(\mathbb{F})$ such that $Q^{-1}AP = B$.

Equivalent matrices can be interpreted as matrices representing the same linear map with respect to different bases. One of the particular form among the equivalent matrices is worth a special mention. Previously we have proved that there exists bases for domain and codomain such that the matrix representation is of the form

\[\begin{pmatrix} I_r & 0 \\ 0 & 0 \\ \end{pmatrix}\]

with $r = r(\alpha)$ being independent of the choices of bases. We can rephrase it as

Proposition. If $A \in \text{Mat}_{n,m}(\mathbb{F})$ then there are invertible matrices $P \in \text{Mat}_m(\mathbb{F})$ and $Q \in \text{Mat}_n(\mathbb{F})$ such that $Q^{-1}AP$ is of the form

\[\begin{pmatrix} I_r & 0 \\ 0 & 0 \\ \end{pmatrix}\]

with $r = r(\alpha)$ is uniquely determined by $A$, i.e. every equivalence class contains precisely one matrix of this form.

Definition. If $A \in \text{Mat}_{n,m}(\mathbb{F})$ then

  • the column rank $r(A)$ of $A$ is the dimension of the subspace of $\mathbb{F}^n$ spanned by the columns of $A$;

  • the row rank of $A$ is the column rank of $A^\intercal$.

The column/row ranks are also the number of linearly independent column/row vectors of the matrix. By definition, we can see that column rank is equal to the rank of the corresponding linear map, i.e. $r(A) = r(\alpha)$ and therefore is constant on equivalence classes.

Proposition. If $A \in \text{Mat}_{n,m}(\mathbb{F})$ then the row rank is equal to column rank, i.e.

\[r(A) = r(A^\intercal)\]

Proof.

Let $r = r(A)$. There exists $P$ and $Q$ such that

\[Q^{-1}AP = \begin{pmatrix} I_r & 0 \\ 0 & 0 \\ \end{pmatrix}\]

Hence,

\[(Q^{-1}AP)^\intercal = P^\intercal A^\intercal (Q^{-1})^\intercal = \begin{pmatrix} I_r & 0 \\ 0 & 0 \\ \end{pmatrix}\]

and $r(A^\intercal) = r = r(A)$.

Proposition. Let $A$ be a $m \times r$ matrix and $B$ be a $r \times n$ matrix. Then

\[r(AB) \le \min(r(A), r(B))\]

Proof.

Let $v$ be a vector in the span of the column vectors of $AB$, i.e.

\[v = \sum_{i = 1}^n \lambda_i (AB)^{(i)} = \sum_{i = 1}^n \lambda_i A B^{(i)} = A \left( \sum_{i=1}^n \lambda_i B^{(i)} \right) = \sum_{j=1}^r \lambda_j' A^{(j)}\]

and $v$ is also in the span of column vectors of $A$ so $r(AB) \le r(A)$.

Similarily, by considering $(AB)^\intercal = B^\intercal A^\intercal$, any vectors in the span of row vectors of $AB$ are also in the span of row vectors of $B$ and $r(AB) \le r(B)$.

Proposition. Let $A$ be a $m \times r$ matrix and $B$ be a $r \times r$ matrix of full-rank. Then

\[r(AB) = r(A)\]

Proof.

Let $a$ be a vector in the span of column vectors of $A$, we have $a = Av$ where $v$ is a $r \times 1$ column matrix of coefficients. Since the $r$ column vectors of $B$ are linearly independent, $v$ is in the span of $B$ with $v = Bu$ where $u$ is also a $r \times 1$ column matrix of coefficients. Thus, we have $a = Av = (AB)u$ and $a$ is also in the span of column vectors of $AB$, i.e. $r(A) \le r(AB)$. Combining with the above conclusion that $r(AB) \le r(A)$, we therefore have $r(AB) = r(A)$.

Similarily, we have $r(AB) = r(B)$ with $A$ being a $r \times r$ matrix of full-rank and $B$ being a $r \times n$ matrix.

Corollary. Let $A$ and $B$ be $n \times n$ matrices of full-rank. Then $AB$ and $BA$ are full-rank.

Elementary Matrices

Definition. The three elementary matrices are the following invertible $n \times n$ matrices

\[\begin{align*} S_{ij}^n &= \begin{pmatrix} 1 & 0 & \cdots & 0 & \cdots & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 & \cdots & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & \cdots & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & \cdots & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & \cdots & 0 & \cdots & 1 \\ \end{pmatrix} \\ \\ E_{ij}^n(\lambda) &= \begin{pmatrix} 1 & 0 & \cdots & 0 & \cdots & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 & \cdots & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & \cdots & \lambda & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & \cdots & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & \cdots & 0 & \cdots & 1 \\ \end{pmatrix} \\ \\ T_{i}^n(\lambda) &= \begin{pmatrix} 1 & 0 & \cdots & 0 & \cdots & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 & \cdots & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda & \cdots & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & \cdots & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & \cdots & 0 & \cdots & 1 \\ \end{pmatrix} \end{align*}\]

If $A$ is an $m \times n$ matrix then

  • $AS_{ij}^n$ swaps the column $i$ and column $j$, $S_{ij}^mA$ swaps the row $i$ and row $j$;

  • $AE_{ij}^n(\lambda)$ adds $\lambda \cdot$(column $i$) to column $j$, $E_{ij}^m(\lambda)A$ adds $\lambda \cdot$(row $j$) to row $i$;

  • $AT_i(\lambda)^n$ multiplies column $i$ by $\lambda$, $T_i^m(\lambda)A$ multiplies column $i$ by $\lambda$.

The elementary matrix represents a column operation when it is on the right and a row operation when it is on the left, base on the matrix multiplication rule that

\[B^{(k)} = AS_{ij} = (S_{ij})_{1k} A^{(1)} + (S_{ij})_{2k} A^{(2)} + ... + (S_{ij})_{nk} A^{(n)}\]

Proposition. If $A \in \text{Mat}_{n,m}(\mathbb{F})$ then there are elementary matrices $E_1^n, … E_a^n$ and $F_1^m, …, F_b^m$ such that

\[E_a^n \cdots E_1^n A F_1^m \cdot F_b^m = \begin{pmatrix} I_r & 0 \\ 0 & 0 \\ \end{pmatrix}\]

Proof.

If $A = 0$ there is nothing to do. Otherwise, we can ensure $A_{11} \not= 0$ by swapping rows $1$ and $i$ and columns $1$ and $j$ so that $A_{ij} \not= 0 \to A_{11}$. We can further ensure $A_{11} = 1$ by multiplying row $1$ by $\lambda = 1 / A_{11}$. We can then add $-A_{1j}$ times column $1$ to column $j$ for each $j$ and add $-A_{i1}$ times row $1$ to row $i$ for each $i$ so the matrix is of the form

\[\begin{pmatrix} 1 & 0 \\ 0 & B \\ \end{pmatrix}\]

We can then do the same to matrix $B$ and by induction we can reduce $A$ to the required form.

This process can be used to actually find $P$ and $Q$ that $Q^{-1}AP$ is of the canonical form. Also, since the three elementary matrix operations do not alter $r(A)$ and $r(A^\intercal)$, it implies that $r(A) = r(A^\intercal) = r(\alpha)$ is independent of the choices of bases.

Reference