基本矩陣

This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.

from lingeo import random_int_list, random_good_matrix

Main idea

Matrix-matrix multipliciation (by row)

Let \(A\) be an \(m\times n\) matrix whose rows are \({\bf r}_1^\top,\ldots,{\bf r}_m^\top\).
Let \(B\) be an \(n\times \ell\) matrix.
Then the rows of \(AB\) are \({\bf r}_1^\top A, \ldots, {\bf r}_m^\top A\).

Let \(A\) be an \(m\times n\) matrix.
One may perform a row operation on \(A\) to obtained \(A'\).

• If \(A\xrightarrow{\rho_i\leftrightarrow\rho_j}A'\) and \(I_n\xrightarrow{\rho_i\leftrightarrow\rho_j}E\), then \(EA = A'\).
• If \(A\xrightarrow{\rho_i: \times k}A'\) and \(I_n\xrightarrow{\rho_i: \times k}E\), then \(EA = A'\).
• If \(A\xrightarrow{\rho_i: +k\rho_j}A'\) and \(I_n\xrightarrow{\rho_i: +k\rho_j}E\), then \(EA = A'\).

These matrices \(E\) generated from \(I_n\) by performing one row operation are called elementary matrices.
The inverse of an elementary matrix is also an elementary matrix, which corresponds to the inverse operation.

If \(A\) reduces to \(R\), then there are \(E_1,\ldots,E_k\), each corresponding to a row operation, such that
\[E_k\cdots E_1A = R. \] In particualr, \(R\) can be chosen as the reduced echelon form of \(A\).

If \(A\) is invertible, then its reduced echelon form is \(I_n\).
Therefore, there are elementary matrices \(E_1,\ldots,E_k\) such that \(E_k\cdots E_1A = I_n\).
That is, every invertible matrix can be written as the product of a sequence of elementary matrices \(E_1^{-1}\cdots E_k^{-1}\).

Side stories

• alternative proof of \(AB = I_n \iff BA = I_n\)
• block row operation
• column operation
• congruent

Experiments

Exercise 1

執行下方程式碼。
矩陣 \(A\) 經過給定的列運算後得到 \(B\)。
求出一個基本矩陣 \(E\) 使得 \(EA = B\)。

### code
set_random_seed(0)
print_ans = False
A = matrix(3, random_int_list(12))
print("A =")
show(A)

B = copy(A)
E = identity_matrix(3)

t = choice([1,2,3])
rows = list(range(3))
shuffle(rows)
i,j = rows[:2]
k = choice([-2,-3,2,3])

if t == 1:
    print("row operation -- row%s <--> row%s"%(i+1,j+1))
    B.swap_rows(i,j)
    E.swap_rows(i,j)
if t == 2:
    print("row operation -- row%s: *%s"%(i+1,k))
    B.rescale_row(i,k)
    E.rescale_row(i,k)
if t == 3:
    print("row operation -- row%s: +%srow%s"%(i+1,k,j+1))
    B.add_multiple_of_row(i,j,k)
    E.add_multiple_of_row(i,j,k)
print("B =")
show(B)

if print_ans:
    print("E =")
    show(E)

給定 seed = 0 時，題目給的數字為

A =
[-4  3  5 -5]
[-5  0  3 -3]
[ 3  4 -4 -3]
 
row operation -- row2: *2
B =
[ -4   3   5  -5]
[-10   0   6  -6]
[  3   4  -4  -3]

答:
因列運算為 row2: *2，
其對應的基本矩陣 \(E\) 為
將單位矩陣執行列運算 row2: *2 後的矩陣，
也就是 \[ E=\begin{bmatrix} 1 &0 & 0 \\ 0 &2 & 0 \\ 0 &0 & 1 \\ \end{bmatrix}. \]

Exercises

Exercise 2

執行以下程式碼。
已知 \(A\) 是可逆的
（所以它的最簡階梯形式是 \(I_3\)）。
寫出一群基本矩陣 \(E_1,\ldots,E_k\)
使得 \(E_k\cdots E_1 A = I_3\)。
（注意先做的列運算
它的基本矩陣要寫在比較靠近 \(A\) 的位置
也就是右邊。）

### code
set_random_seed(0)
A = random_good_matrix(3,3,3)
print("A =")
show(A)

答:
題目給的是
seed=0、\(A=\begin{bmatrix} 1 & 3 & 5\\ -5 & -14 & -30\\ -15 & -42 & -89\\ \end{bmatrix}\)

\(A\xrightarrow{\rho_2: +5\rho_1} \begin{bmatrix} 1 & 3 & 5\\ 0 & 1 & -5\\ -15 & -42 & -89\\ \end{bmatrix} \xrightarrow{\rho_3:+15\rho_1} \begin{bmatrix} 1 & 3 & 5\\ 0 & 1 & -5\\ 0 & 3 & -14\\ \end{bmatrix}\)

\(\xrightarrow{\rho_1:+-3\rho_2} \begin{bmatrix} 　1 & 　0 & 20 \\ 　0 & 　1 & -5 \\ 　0 & 　3 & -14 \\ \end{bmatrix} \xrightarrow{\rho_3:+-3\rho_2} \begin{bmatrix} 1 & 0 & 20\\ 0 & 1 & -5\\ 0 & 0 & 1\\ \end{bmatrix}\)

\(\xrightarrow{\rho_1:+-20\rho_3} \begin{bmatrix} 1 & 0 & 20\\ 0 & 1 & 0\\ 0 & 0 & 1\\ \end{bmatrix} \xrightarrow{\rho_2:+5\rho_3} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ \end{bmatrix}\)

\(E_1 \cdots E_k\) 為 \(\begin{bmatrix} 1 & 0 & 0\\ 5 & 1 & 0\\ 15 & 0 & 1\end{bmatrix} \begin{bmatrix} 1 & -3 & 0\\ 0 & 1 & 0\\ 0 & -3 & 1\end{bmatrix} \begin{bmatrix} 1 & 0 & 5\\ 0 & 1 & -20\\ 0 & 0 & 1\end{bmatrix}.\)

Exercise 3

考慮 \(5\times 5\) 的基本矩陣。

Exercise 3(a)

寫出 \(\rho_1\leftrightarrow\rho_2\) 所對應的基本矩陣、
以及它的反矩陣。

答: \[ E = \begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]

\[ E^{-1} = \begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]

Exercise 3(b)

寫出 \(\rho_1: \times 3\) 所對應的基本矩陣、
以及它的反矩陣。

答: \[ E = \begin{bmatrix} 3 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]

\[ E^{-1} = \begin{bmatrix} \frac{1}{3} & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]

Exercise 3©

寫出 \(\rho_1: +2\rho_2\) 所對應的基本矩陣、
以及它的反矩陣。

答: \[ E = \begin{bmatrix} 1 & 2 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]

\[ E^{-1} = \begin{bmatrix} 1 & -2 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]

Exercise 4

若矩陣 \(M\) 被分割四塊如下
\[\begin{bmatrix} A & B \\ C & D \end{bmatrix},\] 其中 \(A\) 為 \(m\times m\) 方陣並且可逆、
而 \(D\) 為 \(n\times n\) 方陣。

驗證以下的等式
\[\begin{bmatrix} I_m & O \\ -CA^{-1} & I_n \end{bmatrix}\begin{bmatrix} A & B \\ C & D \end{bmatrix} = \begin{bmatrix} A & B \\ O & D - CA^{-1}B \end{bmatrix} \] 這個可視為是對一塊一塊的矩陣做列運算。

答:

區塊矩陣可以把各塊想成數字運算，但要注意乘法的順序。我們可以驗證以下等式
\[ \begin{aligned} I_mA + OC &= A, \\ I_mB + OD &= B, \\ -CA^{-1}A + I_nC &= O, \\ -CA^{-1}B + I_nD &= D-CA^{-1}B \\ \end{aligned} \] 並確認題目所以的等式成立。

Exercise 5

令 \(A\) 和 \(B\) 為 \(n\times n\) 矩陣。
以下步驟提供另一種方式證明︰
若 \(AB = I_n\) 則 \(BA = I_n\)。

Exercise 5(a)

若 \(AB = I_n\)。
證明增廣矩陣 \(\left[\begin{array}{c|c} A & I_n \end{array}\right]\) 的最簡階梯形式矩陣
一定是 \(\left[\begin{array}{c|c} I_n & B \end{array}\right]\)。
若 \(AB = I_n\) 則 \(B = A^{-1}\)且\(BA = I_n\)。

答:

參考 112-4(a)。

Exercise 5(b)

記錄所有的列運算可以得到一群基本矩陣 \(E_1,\ldots, E_k\)。
說明 \(E_k\cdots E_1 A = I_n\) 且 \(E_k\cdots E_1 I_n = B\)﹐
因此 \(BA = I_n\)。

答:

由於 \(\left[\begin{array}{c|c} A & I_n \end{array}\right]\) 的最簡階梯形式矩陣 為 \(\left[\begin{array}{c|c} I_n & B \end{array}\right]\)。 所以存在一群基本矩陣 \(E_1,\ldots,E_k\) 使得\[E_k\cdots E_1 \left[\begin{array}{c|c} A & I_n \end{array}\right] = \left[\begin{array}{c|c} I_n & B \end{array}\right]. \] 也就是 \(E_k\cdots E_1A = I_n\) 且 \(E_k\cdots E_1I_n = B\)。 因此\(B = E_k\cdots E_1\) 且 \(BA = I_n\)。

Exercise 6

相對於列運算﹐
我們也可以自然地定義行運算：

1. swapping: swap the \(i\)-th and the \(j\)-th columns. (Denoted as \(\kappa_i\leftrightarrow\kappa_j\).)
2. rescaling: multiply the \(i\)-th column by a nonzero scalar \(k\). (Denoted as \(\kappa_i:\times k\).)
3. column combination: multiply the \(j\)-th column by a scalar \(k\) and add the result to the \(i\)-th column. (Denoted as \(\kappa_i: + k\kappa_j\).)

令 \(A\) 為一 \(m\times n\) 矩陣。
若 \(A\) 經過某一行運算以後得到 \(A'\)。
而 \(I_n\) 經過同一行運算以後得到 \(E\)。
則 \(AE = A'\)。
（注意列運算基本矩陣乘在左邊﹐用來控制右邊矩陣的列；
而行運算基本矩陣乘在右邊﹐用來控制左邊矩陣的行。）

考慮 \(5\times 5\) 的基本矩陣。

Exercise 6(a)

寫出 \(\kappa_1\leftrightarrow\kappa_2\) 所對應的基本矩陣、
以及它的反矩陣。

\[ E = \begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]

\[ E^{-1} = \begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]

Exercise 6(b)

寫出 \(\kappa_1: \times 3\) 所對應的基本矩陣、
以及它的反矩陣。

\[ E = \begin{bmatrix} 3 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]

\[ E^{-1} = \begin{bmatrix} \frac{1}{3} & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]

Exercise 6©

寫出 \(\kappa_1: +2\kappa_2\) 所對應的基本矩陣、
以及它的反矩陣。

\[ E = \begin{bmatrix} 1 & 0 & 0 & 0 & 0\\ 2 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]

\[ E^{-1} = \begin{bmatrix} 1 & 0 & 0 & 0 & 0\\ -2 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]

Exercise 6(d)

令 \[ J = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \end{bmatrix}\] 且 \[ D = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix}.\]
求一可逆矩陣 \(E\) 使得 \(E^\top JE = D\)。

答:

我們觀察到 \[J\xrightarrow{\rho_2: -\rho_1} \begin{bmatrix} 1 & 1 & 1\\ 0 & 0 & 0\\ 1 & 1 & 1\\ \end{bmatrix} \xrightarrow{\rho_3:-\rho_1} \begin{bmatrix} 1 & 1 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{bmatrix}. \]
因此我們可以找到基本矩陣的乘積 \(E\trans\) 使得 \[ E\trans J = \begin{bmatrix} 1 & 1 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{bmatrix}. \]

對 \(E\trans J\) 做對稱的行運算可發現 \[ E^\top J\xrightarrow{\kappa_2: -\kappa_1} \begin{bmatrix} 1 & 0 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{bmatrix} \xrightarrow{\kappa_3:-\kappa_1} \begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{bmatrix}. \]

所以取 \(E^\top\) 為 \(\xrightarrow{\rho_2: -\rho_1} \xrightarrow{\rho_3:-\rho_1}\) 的基本矩陣，可得 \[ E^\top = \begin {bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \\ \end{bmatrix} \] 以及 \[ E = \begin{bmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \\ \end{bmatrix} \] 使得 \[ E^\top J E = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix}. \]