# 秩與核數

Rank and nullity

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

from lingeo import random_good_matrix

## Main idea

Recall that the number of of pivots of a matrix is the number of nonzero rows in its reduced echelon form.

Let $A$ be an $m\times n$ matrix with $r$ pivots.
Since we know bases of its four fundamental subspaces, we have
1. $\dim(\Row(A)) = \dim(\Col(A)) = r$.
2. $\dim(\ker(A)) = n - r$.
3. $\dim(\ker(A\trans)) = m - r$.

The value $r$ is the **rank** of $A$, denoted as $\rank(A)$,
the value $n - r$ is the **nullity** of $A$, denoted as $\nul(A) = n - r$,
while $m - r$ is usually referred to as the **left nullity** of $A$.

Note that $r$ is also the number of leading variables, and $n - r$ is also the number of free variables.

##### Dimension theorem (matrix form)

Let $A$ be an $m\times n$ matrix.
Then $\rank(A) + \nul(A) = n$, the number of columns.

## Side stories
- low-rank matrix
- row rank and column rank

## Experiments

##### Exercise 1

執行下方程式碼。
試著看出 $A$ 的秩、核數、以及左核數。

<!-- eng start -->
Run the code below. Find the rank, nullity, and the left nullity of $A$.
<!-- eng end -->

---

:::warning

Math error:

What is your $r = 1$? Also, tell the reader what are your $m$ and $n$.

Typesetting:

- [x] Put numbers in math mode `$...$` .
:::

##### Exercise 1(a) - answer here

By running the code above, we obtain that
$$A=\begin{bmatrix}
1 & 5 & -5 & -5 \\
3 & 15 & -14 &-15 \\
6 & 30 & -27 & -29
\end{bmatrix}.$$
By calculation, the Reduced Echelon Form of $A$ is

$$\begin{bmatrix}
1 & 5 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}.
$$
By observing the rref of $A,$
$$\rank(A) =3.$$
Since $A$ is an $m\times n$ matrix with $m = 3$ and $n = 4$, we have

$$
\nul(A) = n - \rank(A) = 1
$$

and

$$
\nul(A\trans) = m - \rank(A) = 0.
$$

---

### code
set_random_seed(0)
print_ans = False
r = choice([3,2,1,0])
m,n,r = 3,4,r
A = random_good_matrix(m,n,r)

print("A =")
show(A)

if print_ans:
    print("rank =", r)
    print("nullity =", n - r)
    print("left nullity =", m - r)

## Exercises

##### Exercise 2

令 $A$ 為一矩陣且其秩為 $r$。
回顧 $r$ 同時是列空間和行空間的維度。
以下討論秩的一些基本性質。

<!-- eng start -->
Let $A$ be a matrix of rank $r$. Recall that $r$ is the dimension of $\Col(A)$ and the dimension of $\Row(A)$. Here we study some basic properties of rank.
<!-- eng end -->

##### Exercise 2(a)

說明 $\rank \begin{bmatrix} A & O \end{bmatrix} =
\rank \begin{bmatrix} A \\ O \end{bmatrix} = r$。
更一般來說 $\rank \begin{bmatrix} A & O \\ O & O \end{bmatrix} = r$。

<!-- eng start -->
Explain why $\rank \begin{bmatrix} A & O \end{bmatrix} = \rank \begin{bmatrix} A \\ O \end{bmatrix} = r$. More generally, $\rank \begin{bmatrix} A & O \\ O & O \end{bmatrix} = r$.
<!-- eng end -->

---

:::warning

Math error:

It is good that you give an example at the beginning, but how exactly do you "apply it to a general case"?

- [x] Then, $\rank\begin{bmatrix} A & O \end{bmatrix}$ is, --> Then, $\begin{bmatrix} A & O \end{bmatrix}$ is (rank is NOT the matrix --- revise this throughout.)

Writing:

- [x] Suppose $A\rightarrow R.$ --> Suppose $A\rightarrow R$, where the arrow means $R$ is the reduced echelon form of $A$.

Typesetting:

- [x] Put numbers in math mode `$...$` .
:::

##### Exercise 2(a) - answer here

Suppose

$$A\space=\begin{bmatrix}
1 & 5 & -5 & -5 \\
3 & 15 & -14 &-15 \\
6 & 30 & -27 & -29
\end{bmatrix}, \space
\rank(A) = 3.
$$
$O$ is a zero matrix of appropriate sizes.

Let

$$
\begin{bmatrix} A & O \end{bmatrix} =
\begin{bmatrix}
1 & 5 & -5 & -5 & 0 & 0 & 0 \\
3 & 15 & -14 & -15 & 0 & 0 & 0\\
6 & 30 & -27 & -29 & 0 & 0 & 0
\end{bmatrix},
$$

then the $rref$ of the above matrix is,
$$\begin{bmatrix}
1 & 5 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0
\end{bmatrix}.
$$

By observation, $\rank \begin{bmatrix} A & O \end{bmatrix} = 3$, for the number of leading variables is $3$.

Same as above, let
$$
\begin{bmatrix} A \\ O\end{bmatrix} =
\begin{bmatrix}
1 & 5 & 0 & 0\\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{bmatrix},
$$
then, by the same reason,
$$\rank \begin{bmatrix} A \\ O \end{bmatrix} = 3.
$$

Again, let

$$
\begin{bmatrix} A & O \\ O & O \end{bmatrix} =
\begin{bmatrix}
1 & 5 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix},
$$

then
$$
\rank \begin{bmatrix} A & O \\ O & O \end{bmatrix}\space =\space 3 .
$$

In the preceding condition, it is clear that

$$
\rank \begin{bmatrix} A & O \end{bmatrix} = \rank \begin{bmatrix} A \\ O \end{bmatrix} =\rank \begin{bmatrix} A & O \\ O & O \end{bmatrix} \space = \space \rank (A) = \space 3.
$$

Thus, we apply it to a general case, where $A$ is a arbitrary $m\times n$ matrix and $O$ is a zero matrix of appropriate sizes.

:::warning

- [x] Let $A\rightarrow R, \space R$ is the reduced echelon form of $A$ . --> Let $A\rightarrow R$, ==where== $R$ is the reduced echelon form of $A$.
- [x] $\begin{bmatrix} A & O \end{bmatrix}\rightarrow\begin{bmatrix} R & O \end{bmatrix},\space and
\begin{bmatrix} A \\ O \end{bmatrix}\rightarrow \begin{bmatrix} R \\ O \end{bmatrix}.$ --> $\begin{bmatrix} A & O \end{bmatrix}\rightarrow\begin{bmatrix} R & O \end{bmatrix}$, and
$\begin{bmatrix} A \\ O \end{bmatrix}\rightarrow \begin{bmatrix} R \\ O \end{bmatrix}.$ (see source code)
- [x] By observing
$R, \space \begin{bmatrix} R & O \end{bmatrix} \space and\begin{bmatrix} R \\ O \end{bmatrix},\space$ --> By observing
$R$, $\begin{bmatrix} R & O \end{bmatrix}$ and $\begin{bmatrix} R \\ O \end{bmatrix}$, (see source code)
:::

Let $A\rightarrow R$, where $R$ is the reduced echelon form of $A$ .

Then,
$\begin{bmatrix} A & O \end{bmatrix}\rightarrow\begin{bmatrix} R & O \end{bmatrix}$, and
$\begin{bmatrix} A \\ O \end{bmatrix}\rightarrow \begin{bmatrix} R \\ O \end{bmatrix}.$

By observing that
$R$, $\begin{bmatrix} R & O \end{bmatrix}$ and $\begin{bmatrix} R \\ O \end{bmatrix}$ have the same number of pivots, we know that
$\rank \begin{bmatrix} A & O \end{bmatrix}=\rank \begin{bmatrix} A \\ O \end{bmatrix}=\rank(A).$

Let

$$
\begin{bmatrix} A & O \\ O & O
\end{bmatrix}
=\begin{bmatrix} B & O \end{bmatrix},
$$

where $B = \begin{bmatrix} A \\ O \end{bmatrix}$. Then, by preceding observation,

$$
\rank\begin{bmatrix} B & O \end{bmatrix} = \rank (B) = \rank (A).
$$

Thus,

$$
\rank \begin{bmatrix} A & O \end{bmatrix} = \rank \begin{bmatrix} A \\ O \end{bmatrix} =\rank \begin{bmatrix} A & O \\ O & O \end{bmatrix} = \space \rank(A).
$$

---

##### Exercise 2(b)

說明對大小適當的矩陣 $B,C,D$ 來說﹐
$\rank \begin{bmatrix} A & B \end{bmatrix} \geq r$ 且
$\rank \begin{bmatrix} A \\ C \end{bmatrix} \geq r$。
更一般來說 $\rank \begin{bmatrix} A & B \\ C & D \end{bmatrix} \geq r$。

<!-- eng start -->
For matrices $B$, $C$, and $D$ of appropriate sizes, show that $\rank \begin{bmatrix} A & B \end{bmatrix} \geq r$ and $\rank \begin{bmatrix} A \\ C \end{bmatrix} \geq r$. More generally, $\rank \begin{bmatrix} A & B \\ C & D \end{bmatrix} \geq r$.
<!-- eng end -->

---

:::warning

Math error:

Combining $A$ with $B$, $C$ and $D$ doesn't affect the $r$ pivots that $rref$ of $A$ has.
The sentence above is vague. What do you mean by the pivots that the _rref_ of $A$ has?

:::

##### Exercise 2(b) - answer here

We know $\dim \Col(A) = \dim \Row(A) = r$. Also, $B$, $C$, and $D$ are matrices of appropriate sizes.

Suppose

$$\begin{bmatrix} A & B \end{bmatrix} =
\begin{bmatrix}
| & & | &| & & |\\
\ba_1 & \cdots &\ba_n&\bb_1& \cdots&\bb_n\\
| & & | &| & & |
\end{bmatrix}.$$
We can see that $\Col(\begin{bmatrix} A & B \end{bmatrix}) \supseteq \Col(A)$ and $\dim\Col(\begin{bmatrix} A & B \end{bmatrix}) \geq \dim\Col(A) = r.$

Suppose $$\begin{bmatrix} A \\ C \end{bmatrix} = \begin{bmatrix}
- & \ba_1 & - \\
~ & \vdots & \\
- & \ba_m & -\\
- & \bc_1 & - \\
~ & \vdots & \\
- & \bc_m & -
\end{bmatrix}.
$$

We can see that $\Row(\begin{bmatrix} A \\ C \end{bmatrix}) \supseteq \Row(A)$ and $\dim\Row(\begin{bmatrix} A \\ C \end{bmatrix}) \geq \dim\Row(A) = r.$

As a result, combining $A$ with $B$, $C$ or $D$ might increase the row space or the column space. In other words, $\dim\Col(A)$ and $\dim\Row(A)$ may increase after combining with $B$, $C$ and $D$.

Therefore,
$\rank \begin{bmatrix} A & B \end{bmatrix} \geq r$,
$\rank \begin{bmatrix} A \\ C \end{bmatrix} \geq r$ and
$\rank \begin{bmatrix} A & B \\ C & D \end{bmatrix} \geq r$.

---

##### Exercise 3

證明所有秩為 $1$ 的 $m\times n$ 矩陣 $A$ 都可寫成 $A = \bu\bv\trans$﹐
其中 $\bu\in\mathbb{R}^m$ 而 $\bv\in\mathbb{R}^n$ 被視為是行向量。

<!-- eng start -->
Show that every $m\times n$ matrix of rank $1$ can be written as $\bu\bv\trans$ for some column vectors $\bu\in\mathbb{R}^m$ and $\bv\in\mathbb{R}^n$.
<!-- eng end -->

---

:::warning

Writing:

- [x] Thus, each row equals to $k\bv\trans$ for some $k$. --> Thus, each row can be written as $k_i\bv$ for some vector $\bv$ and scalar $k_i$.
- [x] What is the purpose of the first sentence "Suppose ..."?

Typesetting:

- [x] Use normal font for numbers, instead of boldface.
- [x] Put math expressions in math mode.
:::

##### Exercise 3 - answer here

According to the question, we know
$\rank(A) = \dim \Row(A) = \dim \Col(A) = 1$.
Therefore, we may assume $\Row(A) = \vspan(\{\bv\trans\})$ for some vector $\bv$.
Thus, each row equals to $k\bv\trans$ for some $k$.

$$A=\begin{bmatrix}
k_1\bv\trans \\
k_2\bv\trans \\
\vdots\\
k_m\bv\trans
\end{bmatrix}
=\begin{bmatrix}
k_1 \\
k_2 \\
\vdots\\
k_m
\end{bmatrix}
\begin{bmatrix}
\bv\trans
\end{bmatrix}.
$$

Therefore, we know every $m\times n$ matrix of rank $1$ can be written as $\bu\bv\trans$ for some column vectors $\bu = \begin{bmatrix}
k_1 \\
k_2 \\
\vdots\\
k_m
\end{bmatrix}\in\mathbb{R}^m$ and $\bv\in\mathbb{R}^n$.

---

##### Exercise 4

如果沒有先前的理論證明﹐很難想像列空間和行空間的維度永遠是一樣的。
（而且它們還一個在 $\mathbb{R}^m$ 中、另一個在 $\mathbb{R}^n$ 裡！）
依照以下的方式再次看出這兩個空間的維度相同。

<!-- eng start -->
Without the theoretical foundation, it is hard to believe that the row space and the column space have the same dimension. (In particular, the row space is in $\mathbb{R}^m$, while the column space is in $\mathbb{R}^n$!) Use the given instructions to show again that their dimensions are the same.
<!-- eng end -->

##### Exercise 4(a)

令 $A$ 為一 $m\times n$ 矩陣、
$Q$ 為一 $m\times m$ 可逆矩陣、
$P$ 為一 $n\times n$ 可逆矩陣。
回顧為什麼 $QA$ 和 $A$ 的列空間相同。
同理 $AP$ 和 $A$ 的行空間相同。

<!-- eng start -->
Let $A$ be an $m\times n$ matrix, $Q$ an $m\times m$ invertible matrix, and $P$ an $n\times n$ invertible matrix. Review why $QA$ and $A$ has the same row space, while $AP$ and $A$ have the same column space.
<!-- eng end -->

---

:::warning

Math:

Wrong direction of inclusion.

Writing:

- [x] , *i.e.* --> . Therefore,
- [x] Since $Q$ is invertible, --> Since $Q$ is invertible, we also have $A = Q^{-1}(QA)$ and
- [x] row column --> row

:::

##### Exercise 4(a) - answer here

Suppose
$$A\space=\begin{bmatrix}
- & \br_1 & - \\
~ & \vdots & \\
- & \br_m & -
\end{bmatrix},
$$

$$
Q = \begin{bmatrix}
q_{11} & \ldots & q_{1m} \\
\vdots & ~ & \vdots \\
q_{m1} & \ldots & q_{mm}
\end{bmatrix},
$$

$$
QA = \begin{bmatrix}
q_{11}\br_1 + q_{12}\br_2 + ... + q_{1m}\br_m \\
\vdots \\
q_{m1}\br_1 + q_{m2}\br_2 + ... + q_{mm}\br_m
\end{bmatrix} .
$$

By observation, it is clear that every row of $QA$ is a linear combination of the row of $A$.
Therefore,

$$
(ⅰ) \space \Row(A) \supseteq \Row(QA).
$$

Since $Q$ is invertible, we also have $A=Q^{-1}(QA).$
Thus,

$$
(ⅱ) \space \Row(A) \subseteq \Row(QA).
$$

By 2 properties, $( ⅰ )$ & $( ⅱ )$,
$$
\space \Row(A) = \Row(QA).
$$

---

##### Exercise 4(b)

令 $Q$ 為一可逆矩陣且
$S = \{\bu_1,\ldots,\bu_k\}$ 是線性獨立的向量集合。
證明 $\{ Q\bu_1,\ldots,Q\bu_k \}$ 也線性獨立。

令 $A$ 為一 $m\times n$ 矩陣、
$Q$ 為一 $m\times m$ 可逆矩陣、
$P$ 為一 $n\times n$ 可逆矩陣。
藉此證明 $AP$ 和 $A$ 的列空間維度相同。
同理 $QA$ 和 $A$ 的行空間維度相同。

<!-- eng start -->
Let $Q$ be an invertible matrix and $S = \{\bu_1,\ldots,\bu_k\}$ a linearly independent set of vectors. Show that $\{ Q\bu_1,\ldots,Q\bu_k \}$ is also linearly independent.

Let $A$ be an $m\times n$ matrix, $Q$ an $m\times m$ invertible matrix, and $P$ an $n\times n$ invertible matrix. Show that the row spaces of $AP$ and $A$ have the same dimension, while the column spaces of $QA$ and $A$ have the same dimension.
<!-- eng end -->

##### Exercise 4(c)

說明任一個 $m\times n$ 矩陣 $A$ 都可以利用列運算及行算運變成

$$
R = \begin{bmatrix}
I_r & O_{r, n-r} \\
O_{m-r, r} & O_{m-r, n-r} \\
\end{bmatrix}.
$$

藉由基本矩陣的幫忙﹐可以找到
$m\times m$ 的可逆矩陣 $E$ 和
$n\times n$ 的可逆矩陣 $F$
使得 $R = E A F$。

<!-- eng start -->
Explain why every $m\times n$ matrix $A$ reduces to

$$
R = \begin{bmatrix}
I_r & O_{r, n-r} \\
O_{m-r, r} & O_{m-r, n-r} \\
\end{bmatrix}
$$

by some row operations and column operations.

By recording the corresponding elementary matrices, one may find an $m\times m$ invertible matrix $E$ and an $n\times n$ invertible matrix such that $R = E A F$.
<!-- eng end -->

##### Exercise 4(d)

可以看出 $R$ 的行空間和列空間維度相同。
證明 $A$ 的行空間和列空間維度也相同。

<!-- eng start -->
It is not hard to see that the row space and the column space of $R$ have the same dimension. Use this fact to show that the row space and the column space of $A$ have the same dimension.
<!-- eng end -->

##### Exercise 5

證明以下關於秩的不等式。

<!-- eng start -->
Prove the following inequalities about rank.
<!-- eng end -->

##### Exercise 5(a)

證明 $\rank(A + B) \leq \rank(A) + \rank(B)$。

<!-- eng start -->
Prove that $\rank(A + B) \leq \rank(A) + \rank(B)$.
<!-- eng end -->

##### Exercise 5(b)

證明 $\rank(AB) \leq \min \{\rank(A), \rank(B)\}$。

<!-- eng start -->
Prove that $\rank(AB) \leq \min \{\rank(A), \rank(B)\}$.
<!-- eng end -->

:::info

collaboration: 1
4 problems: 4

- done: 3, 2(a), 2(b), 4(a)
- pending:

moderator: 1
quality control: 1

:::