# 基本矩陣

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

{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

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)

:::warning

- [x] 第一題也要寫
:::

給定 `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(c)

寫出 $\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}
$$
這個可視為是對一塊一塊的矩陣做列運算。

:::warning

- [x] $A$ 的高度是 $m$
- [x] 這題只要驗證等式成立就好了，如下：
區塊矩陣可以把各塊想成數字運算，但要注意乘法的順序。我們可以驗證以下等式
$$
\begin{aligned}
I_mA + OC &= A, \\
&=
\end{aligned}
$$
並確認題目所以的等式成立。
:::

答:

區塊矩陣可以把各塊想成數字運算，但要注意乘法的順序。我們可以驗證以下等式
$$
\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}
$$
並確認題目所以的等式成立。
<!--
由已知 $A$ 及 $C$ 高為 $n$，
得$-C$ 高為 $n$ 且 $A^{-1}$ 為 $n\times n$ 矩陣。
$－C\cdotp A^{-1} \Longrightarrow$ 計算條件為 $-C$ 寬為 $m$
$\Longrightarrow C$為 $n\times m$ 矩陣
所以 $C$ 為 $n\times m$ 矩陣。
$I_mB=B \Longrightarrow$ $B$ 高為 $m$
$I_nD=D \Longrightarrow$ $D$ 高為 $n$
所以 $A,C$ 寬相同， $B,D$ 也相同，$O\times C_n\tiny\times_m$$\Longrightarrow$寬為 $n$
假設 $O$ 矩陣高不為 $m$
$O\times C$ 高不為 $m$
$I_mA+OC=A$ 不成立
所以 $O$ 高不為 $m$(不成立)。
可知$\begin{bmatrix}
I_m & O \\
-CA^{-1} & I_n
\end{bmatrix}$可視為$(m+n)\times
(m+n)$矩陣。
-->

##### 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$。

:::warning

- [x] 你們的證明沒有用到 $AB = I_n$。把答案改成：參考 112-4(a)。
:::

答:

參考 [112-4(a)](https://hackmd.io/FDeyxV2rR72PJYqYC5DC8w#Exercise-4a)。

##### 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$。

:::warning

- [x] 已知$E_k\cdots E_1 A = 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 = ???$ 且 $??? = I_n$。
- [x] 不要只有數學式，句子要完整。
:::

答:

由於 $\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(c)

寫出 $\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$。

:::warning

- [x] $E$ 沒有可逆
:::

答:

我們觀察到
$$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}.
$$

:::info
1, 4, 5全, 6(d) 要改

目前分數：5.5/5
:::