# 列運算

Row operations

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_int_list, random_good_matrix

## Main idea

Let $A$ be an $m\times n$ matrix $\mathbb{R}^n$.
The following three types of operations on a matrix are called **row operations**.
1. swapping: swap the $i$-th and the $j$-th rows. (Denoted as $\rho_i\leftrightarrow\rho_j$.)
2. rescaling: multiply the $i$-th row by a nonzero scalar $k$. (Denoted as $\rho_i:\times k$.)
3. row combination: multiply the $j$-th row by a scalar $k$ and add the result to the $i$-th row. (Denoted as $\rho_i: + k\rho_j$.)

Note that for $\rho_i: +k\rho_j$, the scalar $k$ can possibly be zero, but then the operation does nothing.

The **pivot** of a row vector is the index of its left-most entry.

A matrix $A$ is in the **echelon form** if:
1. Zero rows are below any nonzero rows.
2. From top to the bottom, the pivot of each row strickly moving to the right.

Each matrix can be reduced to an echelon from through row operations.
If necessary, one may do reduce the matrix further to the form below.

A matrix $A$ is in the **reduced echelon form** if:
1. It is in the echelon form.
2. For each nonzero row, the entry at the pivot is $1$.
3. For each nonzero row, the column of $A$ at the pivot is zero except for the entry on this row.

The **pivots** of a reduced echelon form is the set of pivots of its rows.
The **pivots** of a matrix is the pivots of its reduced echelon form.

If $B$ can be obtained from $A$ by some row reduction, then we say $A$ **reduces to** $B$, denoted as $A\rightarrow B$.
Each matrix reduces to a unique reduced echelon form.

Let $A$ be an $m\times n$ matrix and $\bb$ a vector in $\mathbb{R}^m$.
Then the **augmented matrix** of the equation $A\bx = \bb$ is the $m\times (n+1)$ matrix
$$\left[\begin{array}{c|c} A & \bb \end{array}\right].
$$

## Side stories
- `A.nullspace`
- `A.swap_rows`
- `A.rescale_row`
- `A.add_muptiple_of_row`
- equivalence relation
- equivalence clases

## Experiments

##### Exercise 1
執行下方程式碼。
找到矩陣 $A$ 的最簡階梯形式矩陣。

可以手算也可以考慮在下方程式碼加上：

1. $\rho_i\leftrightarrow\rho_j$: `A.swap_rows(i,j)` .
2. $\rho_i: \times k$: `A.rescale_row(i, k)` .
3. $\rho_i: +k\rho_j$: `A.add_multiple_of_row(i, j, k)` .

<!-- eng start -->
Run the code below. Any find the reduced echelon form of $A$.

You may either do it by hand, or use the code below by adding some lines:

1. $\rho_i\leftrightarrow\rho_j$: `A.swap_rows(i,j)` .
2. $\rho_i: \times k$: `A.rescale_row(i, k)` .
3. $\rho_i: +k\rho_j$: `A.add_multiple_of_row(i, j, k)` .
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False
A, R, pivots = random_good_matrix(3,5,2, return_answer=True)

print("A =")
show(A)

# A.swap_rows(0,1)
# A.rescale_row(1, 1/3)
# A.add_multiple_of_row(1, 0, -3)
print("After row operations:")
show(A)

if print_ans:
    print("The reduced echelon form of A is")
    show(R)

**Answer**

$$
A=
\begin{bmatrix}
1&-3&18&5&-14\\3&8&49&15&-39\\-8&20&-124&-40&100
\end{bmatrix}
$$

OPERATION 1 ： $\rho_2: -3\rho_1$　　　　　　　　　　　↓

$$
～
\begin{bmatrix}
1&-3&18&5&-14\\0&1&-5&0&3\\-8&20&-124&-40&100
\end{bmatrix}
$$

OPERATION 2 ： $\rho_3: +8\rho_1$　　　　　　　　　　　↓

$$
～
\begin{bmatrix}
1&-3&18&5&-14\\0&1&-5&0&3\\0&-4&20&0&-12
\end{bmatrix}
$$

OPERATION 3 ： $\rho_3: +4\rho_2$　　　　　　　　　　　↓

$$
～
\begin{bmatrix}
1&-3&18&5&-14\\0&1&-5&0&3\\0&0&0&0&0
\end{bmatrix}
$$

OPERATION 4 ： $\rho_1: +3\rho_2$　　　　　　　　　　　↓
$$
～
\begin{bmatrix}
1&0&3&5&-5\\0&1&-5&0&3\\0&0&0&0&0
\end{bmatrix}
$$

The Reduced Echelon Form of $A$
$$
＝
\begin{bmatrix}
1&0&3&5&-5\\0&1&-5&0&3\\0&0&0&0&0
\end{bmatrix}
$$

:::warning

- [x] The Reduced Echelon Form of $A$ (put A as $A$)

Have you tried to use the program?
:::

## Exercises

##### Exercise 2

證明每一個列運算都可以被復原。

<!-- eng start -->
Show that any row operation is reversible.
<!-- eng end -->

##### Exercise 2(a)

若 $A$ 經過列運算 $\rho_i\leftrightarrow\rho_j$ 後得到 $B$。
找一個列運算讓 $B$ 變回 $A$。

<!-- eng start -->
Suppose $B$ is obtained from $A$ by applying the row operation $\rho_i\leftrightarrow\rho_j$. Find a row operation that transforms $B$ into $A$.
<!-- eng end -->

:::warning

- [x] Rewrite it with English.
- [x] random --> arbitrary
- [x]
$$
A＝
\begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & & \vdots \\
a_{m1} & \cdots & a_{mn}
\end{bmatrix}
$$

The idea is correct. But $A$ might be an $n\times n$ matrix instead of $2\times 2$.

Examples: Suppose $B$ is obtained from $A$ by applying the row operation $\rho_i\leftrightarrow\rho_j$. Then by swapping the two rows again, $B$ returns to $A$. That is, $A$ can be obtained from $B$ by applying the row operation $\rho_i\leftrightarrow\rho_j$.
:::

$Ans:$
Assume $A$ is a arbitrary $m \times n$ matrix

$$
A＝
\begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & & \vdots \\
a_{m1} & \cdots & a_{mn}
\end{bmatrix}
$$

By doing row operation $\rho_i\leftrightarrow\rho_j$, we will obtain a matrix $B$.
Then by applying the same row operation, $\rho_i\leftrightarrow\rho_j$, to $B$, $B$ will transform back into $A$.

Therefore, we get the conclusion that the row operation which transform $B$ into $A$ is $\rho_i\leftrightarrow\rho_j$.

##### Exercise 2(b)

若 $A$ 經過列運算 $\rho_i: \times k$ 後得到 $B$。
找一個列運算讓 $B$ 變回 $A$。

<!-- eng start -->
Suppose $B$ is obtained from $A$ by applying the row operation $\rho_i: \times k$. Find a row operation that transforms $B$ into $A$.
<!-- eng end -->

:::warning

Again, you have to consider the genral case instead of a particular $A$. Also, your second operation should be $\rho_2: \times \frac{1}{2}$.

- [x] Suppose $A$ is a particular matrix --> We start with an example where $A$ is a particular matrix.
- [x] which $A$ is a random $m\times n$ matrix --> ==where== $A$ is ==an arbitrary== $m\times n$ matrix
- [x] Similar
- [x] the fact --> the observation
- [x] Last paragraph:
Therefore, we get a conclusion that　

:::info
For all $A$, if $B$ is obtained from $A$ by applying the row operation $\rho_i: \times k$, then $B$ will transform back into $A$ by the operation $\rho_i: \times \frac{1}{k}$.

:::

**Answer**

We start with an example where $A$ is a particular matrix.

Let
$$
A=
\begin{bmatrix}
1&2&3&4\\5&6&7&8\\9&10&11&12
\end{bmatrix}
$$

OPERATION 1 ： $\rho_2: \times 2$

$$
～
\begin{bmatrix}
1&2&3&4\\10&12&14&16\\9&10&11&12
\end{bmatrix}
=B
$$
OPERATION 2 ： $\rho_2: \times \frac{1}{2}$

$$
～
\begin{bmatrix}
1&2&3&4\\5&6&7&8\\9&10&11&12
\end{bmatrix}
=A
$$

In the preceding condition, it is clear that after transforming $A$ into $B$, by doing $\rho_2: ×2$, we are able to transform $B$ back into $A$, by doing $\rho_2: \times \frac{1}{2}$.

Thus, we apply the preceding procedure into a general case, where $A$ is a arbitrary $m\times n$ matrix, and $B$ is a matrix obtained from $A$ by applying row operation $\rho_i: \times k$.

Similar to the observation on the particular $A$, we are able to transform $B$ back into $A$ by doing $\rho_i: \times \frac{1}{k}$.

Therefore, we get a conclusion that　

:::info
For all $A$, if $B$ is obtained from $A$ by applying the row operation $\rho_i: \times k$, then $B$ will transform back into $A$ by the operation $\rho_i: \times \frac{1}{k}$.
:::

##### Exercise 2(c)

若 $A$ 經過列運算 $\rho_i: + k\rho_j$ 後得到 $B$。
找一個列運算讓 $B$ 變回 $A$。

<!-- eng start -->
Suppose $B$ is obtained from $A$ by applying the row operation $\rho_i: + k\rho_j$. Find a row operation that transforms $B$ into $A$.
<!-- eng end -->

:::warning

Same issue. What is the opposite operation of $\rho_i: + k\rho_j$.

- [x] random --> arbitrary
- [x] It is okay to remove the second paragraph.
:::

**Answer**

Assuming that $A$ is a arbitrary $m\times n$ matrix, which means that it could be applied in any general cases, and $B$ is a matrix obtained from $A$ by applying row operation $\rho_i: +k\rho_j$. By applying row operation $\rho_i: -k\rho_j$, $B$ returns to $A$. Therefore, the opposite operation of $\rho_i: +k\rho_j$ should be $\rho_i: -k\rho_j$.

##### Exercise 3

令 $A$ 為一矩陣其各列向量為 $\br_1,\ldots,\br_m$。
依照下面的步驟證明列運算不會改變列空間。

<!-- eng start -->
Let $A$ be a matrix and $\br_1,\ldots,\br_m$ its rows. Use the given instructions to prove that row operations do not change the row space.
<!-- eng end -->

##### Exercise 3(a)

若 $A$ 經過列運算 $\rho_i\leftrightarrow\rho_j$ 後得到 $B$。
證明 $\Row(A) = \Row(B)$。

<!-- eng start -->
Suppose $B$ is obtained from $A$ by applying the row operation $\rho_i\leftrightarrow\rho_j$. Show that $\Row(A) = \Row(B)$.
<!-- eng end -->

##### Exercise 3(b)

若 $A$ 經過列運算 $\rho_i: \times k$ 後得到 $B$。
證明 $\Row(A) = \Row(B)$。

<!-- eng start -->
Suppose $B$ is obtained from $A$ by applying the row operation $\rho_i: \times k$. Show that $\Row(A) = \Row(B)$.
<!-- eng end -->

##### Exercise 3(c)

若 $A$ 經過列運算 $\rho_i: + k\rho_j$ 後得到 $B$。
證明 $\Row(A) = \Row(B)$。

<!-- eng start -->
Suppose $B$ is obtained from $A$ by applying the row operation $\rho_i: + k\rho_j$. Show that $\Row(A) = \Row(B)$.
<!-- eng end -->

##### Exercise 4

令 $A$ 為一矩陣其各列向量為 $\br_1,\ldots,\br_m$
而 $\bb = (b_1,\ldots,b_m)\trans$。
令 $A'$ 為方程組 $A\bx = \bb$ 增廣矩陣。
依照下面的步驟證明列運算不會改變解集合。

<!-- eng start -->
Let $A$ be a matrix and $\br_1,\ldots,\br_m$ its rows. Let $\bb = (b_1,\ldots,b_m)\trans$. Let $A'$ be the augmented matrix of $A\bx = \bb$. Use the given instructions to prove that row operations do not change the row space.
<!-- eng end -->

##### Exercise 4(a)

若 $A'$ 經過列運算 $\rho_i\leftrightarrow\rho_j$ 後得到 $B'$。
證明兩增廣矩陣對應到的方程組有一樣的解集合。

<!-- eng start -->
Suppose $B'$ is obtained from $A'$ by applying the row operation $\rho_i\leftrightarrow\rho_j$. Show that the two systems of linear equations corresponding to $A'$ and $B'$ have the same solution set.
<!-- eng end -->

##### Exercise 4(b)

若 $A'$ 經過列運算 $\rho_i: \times k$ 後得到 $B'$。
證明兩增廣矩陣對應到的方程組有一樣的解集合。

<!-- eng start -->
Suppose $B'$ is obtained from $A'$ by applying the row operation $\rho_i: \times k$. Show that the two systems of linear equations corresponding to $A'$ and $B'$ have the same solution set.
<!-- eng end -->

##### Exercise 4(c)

若 $A$ 經過列運算 $\rho_i: + k\rho_j$ 後得到 $B$。
證明兩增廣矩陣對應到的方程組有一樣的解集合。

<!-- eng start -->
Suppose $B'$ is obtained from $A'$ by applying the row operation $\rho_i: + k\rho_j$. Show that the two systems of linear equations corresponding to $A'$ and $B'$ have the same solution set.
<!-- eng end -->

##### Exercise 5

依照下面的步驟證明「可化簡到」是一個**等價關係** 。

<!-- eng start -->
Use the given instructions to prove that "reduce to" is an **equivalence relation** .
<!-- eng end -->

##### Exercise 5(a)

證明反身性：
$A\rightarrow A$。

<!-- eng start -->
Prove that "reduce to" is reflexive: $A\rightarrow A$.
<!-- eng end -->

##### Exercise 5(b)

證明對稱性：
若 $A\rightarrow B$﹐則 $B\rightarrow A$。

<!-- eng start -->
Prove that "reduce to" is symmetric: If $A\rightarrow B$, then $B\rightarrow A$.
<!-- eng end -->

##### Exercise 5(c)

證明遞移性：
若 $A\rightarrow B$ 且 $B\rightarrow C$，則 $A\rightarrow C$。

<!-- eng start -->
Prove that "reduce to" is transitive: If $A\rightarrow B$ and $B\rightarrow C$, then $A\rightarrow C$.
<!-- eng end -->

##### Exercise 5(d)

如此一來「可化簡到」可以幫所有 $m\times n$ 矩陣分類：
隨便拿出一個 $m\times n$ 矩陣 $A$，取出所有可以從 $A$ 化簡到的矩陣﹐如此一來會形成一個**等價類** 。
若 $\mathcal{M}_{m\times n}$ 為所有 $m\times n$ 矩陣的集合，
我們通常用 $\mathcal{M}_{m\times n} / \rightarrow$ 來表示所有等價類所形成的集合。
利用最間階梯形式矩陣是唯一的這個性質，來說明怎麼判斷兩個矩陣是否落在同一個等價類中。

<!-- eng start -->
As a consequence, "reduce to" gives a partition to the set of $m\times n$ matrices: For any $m\times n$ matrix $A$, the set of matrices that $A$ reduces to is called an **equivalence class** . Let $\mathcal{M}_{m\times n}$ be the set of all $m\times n$ matrices. Then we define $\mathcal{M}_{m\times n} / \rightarrow$ as the set of all equivalence classes. Recall that every matrix has a unique reduced echelon form. Use this fact to provide a method that can determines whether two matrices are in the same equivalence class.
<!-- eng end -->

##### Exercise 6

若 $A$ 是一個 $m\times n$ 矩陣。
證明 $A$ 可以化簡到的最簡階梯形式矩陣是唯一的。

<!-- eng start -->
Let $A$ be an $m\times n$ matrix. Show that $A$ reduces to a unique reduced echelon form.
<!-- eng end -->

##### Exercise 6(a)

證明「$A$ 可以化簡到的最簡階梯形式矩陣是唯一的。」這個敘述在 $n=1$ 時是正確的。

<!-- eng start -->
Show that the statement "$A$ reduces to a unique reduced echelon form" is correct when $n = 1$.
<!-- eng end -->

##### Exercise 6(b)

假設「$A$ 可以化簡到的最簡階梯形式矩陣是唯一的。」這個敘述在 $n=k$ 時是正確的。
考慮一個 $n=k+1$ 的矩陣，並它寫成 $\begin{bmatrix} A' & \ba\end{bmatrix}$。
根據假設，$A'$ 的最簡階梯式是唯一的，我們把它記作 $R'$。
說明 $A$ 化簡到最簡階梯形式時會是 $\begin{bmatrix} R' & \br\end{bmatrix}$。
（因此唯一有可能不一樣的就是最後一行。）

<!-- eng start -->
Suppose the statement "$A$ reduces to a unique reduced echelon form" is correct when $n = k$. Then we consider a matrix with $n = k+1$, and we may write it as $\begin{bmatrix} A' & \ba\end{bmatrix}$. By the assumption, the reduced echelon form of $A'$ is unique, say it is $R'$. Show that the reduced echelon form of $A$ has the form $\begin{bmatrix} R' & \br\end{bmatrix}$. (That is, if the reduced echelon form is not unqiue, then the only potential differences occur in the last column.)
<!-- eng end -->

##### Exercise 6(c)

我們把 $R'$ 的行寫成 $\bu_1,\ldots,\bu_k$。

考慮兩種狀況：
首先，若 $\ker(A)$ 中有一個向量 $\bv = (c_1,\ldots, c_{k+1})$ 其 $c_{k+1}\neq 0$。
利用 $\ker(A) = \ker\left(\begin{bmatrix} R' & \br \end{bmatrix}\right)$
說明 $\br = -\frac{1}{c_{k+1}}(c_1\bu_1 + \cdots + c_k\bu_k)$ 是唯一的選擇。

<!-- eng start -->
Let $\bu_1,\ldots,\bu_k$ be the columns of $R'$.

Consider two cases:

The first case is when there is a vector $\bv = (c_1,\ldots, c_{k+1})$ in $\ker(A)$ such that $c_{k+1}\neq 0$. Use the fact that $\ker(A) = \ker\left(\begin{bmatrix} R' & \br \end{bmatrix}\right)$ to show that $\br = -\frac{1}{c_{k+1}}(c_1\bu_1 + \cdots + c_k\bu_k)$ is the unique choice for the last column of the reduced echelon form.
<!-- eng end -->

##### Exercise 6(d)

第二種狀況，$\ker(A)$ 中的所有向量 $\bv = (c_1,\ldots, c_{k+1})$ 都是 $c_{k+1} = 0$。
說明這種狀況下 $\ba\notin\Col(A')$ 且 $\br\notin\Col(R')$。
如果 $R'$ 有 $h$ 個非零的列，說明 $\br$ 一定在第 $h+1$ 項是 $1$ 而其它項都是 $0$。

<!-- eng start -->
The second case is when every vector $\bv = (c_1,\ldots, c_{k+1})$ in $\ker(A)$ has $c_{k+1}= 0$. Show that $\ba\notin\Col(A')$ and $\br\notin\Col(R')$. Therefore, $\br$ must be a vector whose $(h+1)$-entry is $1$ while other entries are zero, where $h$ is the number of nonzero rows in $R'$.
<!-- eng end -->

:::info

collaboration: 2
3 problems: 3

quality control: 1
moderator: 1
:::