Row operations
This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
$\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
Let $A$ be an $m\times n$ matrix $\mathbb{R}^n$.
The following three types of operations on a matrix are called row operations.
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:
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:
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].$$
A.nullspace
A.swap_rows
A.rescale_row
A.add_muptiple_of_row
執行下方程式碼。
找到矩陣 $A$ 的最簡階梯形式矩陣。
可以手算也可以考慮在下方程式碼加上:
A.swap_rows(i,j)
.A.rescale_row(i, k)
.A.add_multiple_of_row(i, j, k)
.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:
A.swap_rows(i,j)
.A.rescale_row(i, k)
.A.add_multiple_of_row(i, j, k)
.### 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)
若 $A$ 經過列運算 $\rho_i\leftrightarrow\rho_j$ 後得到 $B$。
找一個列運算讓 $B$ 變回 $A$。
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$.
若 $A$ 經過列運算 $\rho_i: \times k$ 後得到 $B$。
找一個列運算讓 $B$ 變回 $A$。
Suppose $B$ is obtained from $A$ by applying the row operation $\rho_i: \times k$. Find a row operation that transforms $B$ into $A$.
若 $A$ 經過列運算 $\rho_i: + k\rho_j$ 後得到 $B$。
找一個列運算讓 $B$ 變回 $A$。
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$.
令 $A$ 為一矩陣其各列向量為 $\br_1,\ldots,\br_m$。
依照下面的步驟證明列運算不會改變列空間。
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.
若 $A$ 經過列運算 $\rho_i\leftrightarrow\rho_j$ 後得到 $B$。
證明 $\Row(A) = \Row(B)$。
Suppose $B$ is obtained from $A$ by applying the row operation $\rho_i\leftrightarrow\rho_j$. Show that $\Row(A) = \Row(B)$.
若 $A$ 經過列運算 $\rho_i: \times k$ 後得到 $B$。
證明 $\Row(A) = \Row(B)$。
Suppose $B$ is obtained from $A$ by applying the row operation $\rho_i: \times k$. Show that $\Row(A) = \Row(B)$.
若 $A$ 經過列運算 $\rho_i: + k\rho_j$ 後得到 $B$。
證明 $\Row(A) = \Row(B)$。
Suppose $B$ is obtained from $A$ by applying the row operation $\rho_i: + k\rho_j$. Show that $\Row(A) = \Row(B)$.
令 $A$ 為一矩陣其各列向量為 $\br_1,\ldots,\br_m$
而 $\bb = (b_1,\ldots,b_m)\trans$。
令 $A'$ 為方程組 $A\bx = \bb$ 增廣矩陣。
依照下面的步驟證明列運算不會改變解集合。
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.
若 $A'$ 經過列運算 $\rho_i\leftrightarrow\rho_j$ 後得到 $B'$。
證明兩增廣矩陣對應到的方程組有一樣的解集合。
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.
若 $A'$ 經過列運算 $\rho_i: \times k$ 後得到 $B'$。
證明兩增廣矩陣對應到的方程組有一樣的解集合。
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.
若 $A$ 經過列運算 $\rho_i: + k\rho_j$ 後得到 $B$。
證明兩增廣矩陣對應到的方程組有一樣的解集合。
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.
依照下面的步驟證明「可化簡到」是一個等價關係 。
Use the given instructions to prove that "reduce to" is an equivalence relation .
證明對稱性:
若 $A\rightarrow B$﹐則 $B\rightarrow A$。
Prove that "reduce to" is symmetric: If $A\rightarrow B$, then $B\rightarrow A$.
證明遞移性:
若 $A\rightarrow B$ 且 $B\rightarrow C$,則 $A\rightarrow C$。
Prove that "reduce to" is transitive: If $A\rightarrow B$ and $B\rightarrow C$, then $A\rightarrow C$.
如此一來「可化簡到」可以幫所有 $m\times n$ 矩陣分類:
隨便拿出一個 $m\times n$ 矩陣 $A$,取出所有可以從 $A$ 化簡到的矩陣﹐如此一來會形成一個等價類 。
若 $\mathcal{M}_{m\times n}$ 為所有 $m\times n$ 矩陣的集合,
我們通常用 $\mathcal{M}_{m\times n} / \rightarrow$ 來表示所有等價類所形成的集合。
利用最間階梯形式矩陣是唯一的這個性質,來說明怎麼判斷兩個矩陣是否落在同一個等價類中。
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.
若 $A$ 是一個 $m\times n$ 矩陣。
證明 $A$ 可以化簡到的最簡階梯形式矩陣是唯一的。
Let $A$ be an $m\times n$ matrix. Show that $A$ reduces to a unique reduced echelon form.
證明「$A$ 可以化簡到的最簡階梯形式矩陣是唯一的。」這個敘述在 $n=1$ 時是正確的。
Show that the statement "$A$ reduces to a unique reduced echelon form" is correct when $n = 1$.
假設「$A$ 可以化簡到的最簡階梯形式矩陣是唯一的。」這個敘述在 $n=k$ 時是正確的。
考慮一個 $n=k+1$ 的矩陣,並它寫成 $\begin{bmatrix} A' & \ba\end{bmatrix}$。
根據假設,$A'$ 的最簡階梯式是唯一的,我們把它記作 $R'$。
說明 $A$ 化簡到最簡階梯形式時會是 $\begin{bmatrix} R' & \br\end{bmatrix}$。
(因此唯一有可能不一樣的就是最後一行。)
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.)
我們把 $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)$ 是唯一的選擇。
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.
第二種狀況,$\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$。
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'$.