# 基本矩陣與行超平行體

Elementary matrix acts on columns

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, row_operation_process

## Main idea

Each $n\times n$ matrix can be viewed as a list of column vectors $\{\bu_1,\ldots, \bu_n\}$.
We define the **column parallelotope** of $A$ as the polytope

$$
\{c_1\bu_1 + \cdots + c_n\bu_n : c_i\in [0,1] \text{ for all }i = 1,\ldots, n\}
$$

spanned by the columns $\{\bu_1,\ldots, \bu_n\}$ of $A$.
Let $\Vol_C(A)$ be the **signed volume** of the column parallelotope.

Then $\Vol_C(A)$ can be defined through the following rules.

- $\Vol_C(I_n) = 1$.
- If $E$ is the elementary matrix of $\rho_i\leftrightarrow\rho_j$, then $E$ **swaps** the $i$-th and $j$-th coordinates of columns of $A$.
Thus, $\Vol_C(EA) = -\Vol_C(A)$ and we define $\Vol_C(E) = -1$.
- If $E$ is the elementary matrix of $\rho_i:\times k$, then $E$ **rescales** the $i$-th coordinates of columns of $A$.
Thus, $\Vol_C(EA) = k\Vol_C(A)$ and we define $\Vol_C(E) = k$.
(Note that this statement still holds even when $k = 0$.)
- If $E$ is the elementary matrix of $\rho_i:+k\rho_j$, then $E$ **slants** the $i$-th coordinates of columns of $A$ to the direction of $j$-th coordinates.
Thus, $\Vol_C(EA) = \Vol_C(A)$ and we define $\Vol_C(E) = 1$.

As a consequence, if a matrix $A$ is invertible and
can be written as the product a sequence of elementary matrices $F_1\cdots F_k$,
then $\Vol_C(A) = \Vol_C(F_1)\cdots\Vol_C(F_k)\Vol_C(I_n) = \Vol_C(F_1)\cdots\Vol_C(F_k)$.

In contrast, if $A$ is not invertible,
then column parallelotope collapses and is flat $\Vol_C(A) = 0$.

From this point of view,
the value of $\Vol_C(A)$ can be both
the signed volume and
the **scaling factor** changing $\Vol_C(B)$ to $\Vol_C(AB)$ for any $B$.

## Side stories
- Jacobian

## Experiments

##### Exercise 1

執行以下程式碼。
已知 $A = F_1\cdots F_k$ 是一群單位矩陣的乘積。

<!-- eng start -->
Run the code below. Suppose we know $A = F_1\cdots F_k$ is the product of some elementary matrices.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False

n = 2
while True:
    A = matrix(n, random_int_list(n^2, 3))
    if A.det() != 0:
        break
        
elems = row_operation_process(A, inv=True)

pretty_print(A, LatexExpr("="), *elems)

R = identity_matrix(n)
k = 1
vols = [1]
for elem in elems[::-1]:
    R = elem * R
    vols.append(R.det())
    vecs = R.columns()
    P = polytopes.parallelotope(vecs).plot(
        xmin=-3, 
        xmax=3,
        ymin=-3,
        ymax=3,
        wireframe="black", 
        fill="lightgreen"
    )
    for v in vecs:
        P += text("%s"%v, v + vector([0,0.5]), fontweight=1000).plot()
    show(P, title="$V_{%s}$"%k)
    k += 1

if print_ans:
    for k,vol in enumerate(vols):
        print("The signed volumn (volume) of V%s is"%k, vol)

By running the code above with `seed=0`, we get
$$
\begin{bmatrix}-3&3\\1&2\end{bmatrix}=\begin{bmatrix}-3&0\\0&1\end{bmatrix}\begin{bmatrix}1&0\\1&1\end{bmatrix}\begin{bmatrix}1&0\\0&3\end{bmatrix}\begin{bmatrix}1&-1\\0&1\end{bmatrix}.
$$

##### Exercise 1(a)

令 $V_0$ 為單位矩陣的行超平行體。
說明如何從 $V_0$ 得到 $V_1$ 並求出 $V_1$ 的面積。

<!-- eng start -->
Let $V_0$ be the column parallelotope for the identity matrix. Explain how to obtain $V_1$ from $V_0$ and find the volume of $V_1$.
<!-- eng end -->

**Solution:**
Since $V_0$ is the column parallelotope for the identity matrix,
$$
V_0
=\begin{bmatrix}\
1 & 0 \\
0 & 1
\end{bmatrix}.
$$

$$
V_1
=\begin{bmatrix}
1 & -1 \\
0 & 1
\end{bmatrix}=
\begin{bmatrix}
1 & -1 \\
0 & 1
\end{bmatrix}\begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix}.
$$
$\begin{bmatrix}1 & -1 \\0 & 1 \end{bmatrix}$ is the elementary matrix of $\rho_2:+(-1)\rho_1$, so it slants.
Therefore, volume will not be changed.

Thus,
$$
\Vol_C(V_1)=1.
$$

##### Exercise 1(b)

依序說明如何從 $V_i$ 得到 $V_{i+1}$，
並求出 $V_2,\ldots, V_k$ 的面積。

<!-- eng start -->
Explain how to obtain $V_{i+1}$ from $V_i$ and find the volume of $V_{i+1}$ for each $i$. Then find the volume for each of $V_2,\ldots, V_k$.
<!-- eng end -->

**Solution:**
$$
V_2
=\begin{bmatrix}
1 & -1 \\
0 & 3
\end{bmatrix}
=\begin{bmatrix}
1 & 0 \\
0 & 3
\end{bmatrix}
\begin{bmatrix}
1 & -1 \\
0 & 1
\end{bmatrix}.
$$
$\begin{bmatrix}
1 & 0 \\
0 & 3
\end{bmatrix}$ is the elementary matrix of $\rho_2:\times3$, so it rescales.
Therefore, volume will rescale three times larger which is $3$.

Thus,
$$
\Vol_C(V_2)=3.
$$

$$
V_3
=\begin{bmatrix}
1 & -1 \\
1 & 2
\end{bmatrix}
=\begin{bmatrix}
1 & 0 \\
1 & 1
\end{bmatrix}
\begin{bmatrix}
1 & -1 \\
0 & 3
\end{bmatrix}.
$$
$\begin{bmatrix}
1 & 0 \\
1 & 1
\end{bmatrix}$ is the elementary matrix of $\rho_1:+(1\rho_2)$, so it slants.
Therefore, volume will not be changed.
Thus,
$$
\Vol_C(V_3)=3.
$$

$$
V_4
=\begin{bmatrix}
-3 & 3 \\
1 & 2
\end{bmatrix}
=\begin{bmatrix}
-3 & 0 \\
0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & -1 \\
1 & 2
\end{bmatrix}.
$$
$\begin{bmatrix}
-3 & 0 \\
0 & 1
\end{bmatrix}$ is the elementary matrix of $\rho_1:\times (-3)$, so it rescales.
Therefore, volume will rescale minus three times larger.

Thus,
$$
\Vol_C(V_4)=-9.
$$

:::info
What do the experiments try to tell you? (open answer)

The solution tell us that the volume of the column parallelotope is equal to the determinant of the matrix.
:::

## Exercises

##### Exercise 2

對以下矩陣 $A$，
用文字描述它的行平行體，並用求出它的有向體積。

<!-- eng start -->
For each of the following matrices $A$, use a few sentences to decribe its column parallelotope. Then find its signed volumn.
<!-- eng end -->

##### Exercise 2(a)

$$
A = \begin{bmatrix}
1 & 0 & 0 \\
0 & 2 & 0 \\
0 & 0 & 3
\end{bmatrix}.
$$

A:
This column parallelotope is made up by three vectors $(1,0,0),(0,2,0),(0,0,3)$.
It is a rectangular cuboid with the length $1,2,3$.
Thus,
$$
\Vol_C(A)=6.
$$

##### Exercise 2(b)

$$
A = \begin{bmatrix}
0 & 1 & 0 \\
2 & 0 & 0 \\
0 & 0 & 3
\end{bmatrix}.
$$

A:
This column parallelotope is made up by three vectors $(0,2,0),(1,0,0),(0,0,3)$.
It is a rectangular cuboid with the length $1,2,3$.
Because of the exchange $\rho_1\leftrightarrow\rho_2$, the value must be negative.
Thus,
$$
\Vol_C(A)=-6.
$$

:::warning

- [x] Wrong vectors.
:::

##### Exercise 2(c)

$$
A = \begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 3 \\
0 & 0 & 0
\end{bmatrix}.
$$

A:
This column parallelotope is made up by three vector $(1,1,0),(1,2,0),(1,3,0)$.
Because z-coordinates of three vectors are all $0$, it lays on the plane $z=0$.
Thus,
$$
\Vol_C(A)=0.
$$

:::warning

- [x] Wrong vectors?
- [x] the $z$-coordinates of three vectors
- [x] it lays on
:::

##### Exercise 2(d)

$$
A = \begin{bmatrix}
1 & 1 & 0 \\
1 & 2 & 0 \\
1 & 3 & 0
\end{bmatrix}.
$$

A:
This column parallelotope is made up by three vector $(1,1,1),(1,2,3),(0,0,0)$.
Because three vectors are all on the same plane $x-2y+z=0$.
Thus,
$$
\Vol_C(A)=0.
$$

:::warning

- [x] Wrong vectors.
:::

##### Exercise 2(e)

$$
A = \begin{bmatrix}
1 & 2 & 0 \\
3 & 4 & 0 \\
0 & 0 & 5
\end{bmatrix}.
$$

A:
It is a rectangular cuboid made up by three vectors $(1,3,0),(2,4,0),(0,0,5)$.
We use $\rho_2:+(-2)\times\rho_1$, then we get
$$
\begin{bmatrix}
1 & 0 & 0 \\
3 & -2 & 0 \\
0 & 0 & 5
\end{bmatrix}.
$$
Let $\rho_1:+\frac{3}{2}\rho_2$, we get
$$
\begin{bmatrix}
1 & 0 & 0 \\
0 & -2 & 0 \\
0 & 0 & 5
\end{bmatrix}.
$$
Thus,
$$
\Vol_C(A)=-10.
$$

:::warning

- [x] Wrong vectors.
:::

##### Exercise 3

在 $\Vol_C$ 的定義中，假設我們已經接受了

- If $E$ is the elementary matrix of $\rho_i:\times k$, then $E$ **rescales** the $i$-th coordinates of columns of $A$.
- If $E$ is the elementary matrix of $\rho_i:+k\rho_j\times$, then $E$ **slants** the $i$-th coordinates of columns of $A$ to the direction of $j$-th coordinates.

說明為什麼

- If $E$ is the elementary matrix of $\rho_i\leftrightarrow\rho_j$, then $E$ **swaps** the $i$-th and $j$-th coordinates of columns of $A$.

中的 $-1$ 是合理的。

<!-- eng start -->
In the definition of $\Vol_C$, suppose we already accept the following rules.

- If $E$ is the elementary matrix of $\rho_i:\times k$, then $E$ **rescales** the $i$-th coordinates of columns of $A$.
- If $E$ is the elementary matrix of $\rho_i:+k\rho_j\times$, then $E$ **slants** the $i$-th coordinates of columns of $A$ to the direction of $j$-th coordinates.

Explain the $-1$ in the rule below is reasonable.

- If $E$ is the elementary matrix of $\rho_i\leftrightarrow\rho_j$, then $E$ **swaps** the $i$-th and $j$-th coordinates of columns of $A$.
<!-- eng end -->

**Solution:**

Assume that $A$ has $n$ row, and $\br_i$ is a zero row in $A$, $i\in [1,n]$.
$$
A=
\begin{bmatrix}
- & \br_1 & - \\
- & \br_2 & - \\
- & \vdots & - \\
- & \br_i & - \\
- & \vdots & - \\
- & \br_n & - \\
\end{bmatrix}.
$$

Let $\rho_i:\times 2$, then we get
$$
A^{\prime}=
\begin{bmatrix}
- & \br_1 & - \\
- & \br_2 & - \\
- & \vdots & - \\
- & 2\times\br_i & - \\
- & \vdots & - \\
- & \br_n & - \\
\end{bmatrix}.
$$
Therefore, $2\times\Vol_C(A)=\Vol_C(A^{\prime})$.

Since $\br_i$ is a zero row, $2\times\br_i=\br_i$, $A=A^{\prime}$.

In other word, $\Vol_C(A)=\Vol_C(A^{\prime})=2\times\Vol_C(A)$.

Thus, $\Vol_C(A)=0$.

##### Exercise 4

利用 $\Vol_C$ 定義中的四條準則，說明以下性質。

<!-- eng start -->
Use the four rules in the definition of $\Vol_C$ to expalin the following properties.
<!-- eng end -->

##### Exercise 4(a)

若 $A$ 中有一列為零向量，說明 $\Vol_C(A) = 0$。

<!-- eng start -->
If $A$ has a zero row, then $\Vol_C(A) = 0$.
<!-- eng end -->

:::warning

:warning: $A$ might not have the given representation. For example, $A = \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}$.
:::

**Solution:**
By the definition, we know that $\Vol_C(I_n)=1$.
Let $E$ is the elementary matrix of $\rho_i:\times0 ,i \in [0,n]$, then E rescales the i-th coordinates of columns.
Therefore,
$$
\Vol_C(EI_n)=0\times\Vol_C(I_n)
=0.
$$
And by the definition,
$$
\Vol_C(E)=0.
$$

Because every row in the $I_n$ has only one non-zero element, after E rescales we get a zero row.

For any $n\times n$ matrix A that has a zero row, we can find that $A=F_1\cdots F_k\times E\times I_n$ is the product of some elementary matrices.

Thus,
$$
\Vol_C(A)=\Vol_C(F_1)\cdots \Vol_C(F_k) \times \Vol_C(E) \times \Vol_C(I_n)\\=
\Vol_C(F_1)\cdots \Vol_C(F_k) \times 0 \times 1 \\
=0.
$$

##### Exercise 4(b)

若 $A$ 中有兩列向量相等，說明 $\Vol_C(A) = 0$。

<!-- eng start -->
If $A$ has two rows in common, then $\Vol_C(A) = 0$.
<!-- eng end -->
**Solution:**
We can do the column operation to kill one of the same column.
In other word, we only slants the volume.
Therefore the volume will not be changed.
And we get a zero column which is same as exercise4(a).
Thus,
$$
\Vol_C(A) = 0.
$$
##### Exercise 4(c)

若 $A$ 中的列向量集合線性相依，說明 $\Vol_C(A) = 0$。

<!-- eng start -->
If some rows of $A$ form a linearly dependent set, then $\Vol_C(A) = 0$.
<!-- eng end -->
**Solution:**
Since some rows of A form a linearly dependent set, we can do some column operations to kill some columns which made some columns into zero columns.
Thus, we have the condition same as exercise4(a).
Thus,
$$
\Vol_C(A) = 0.
$$
##### Exercise 5

令

$$
A = \begin{bmatrix}
\frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}}\\
\frac{1}{\sqrt{3}} & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}}\\
\frac{1}{\sqrt{3}} & 0 & -\frac{2}{\sqrt{6}}\\
\end{bmatrix}.
$$

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
\frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}}\\
\frac{1}{\sqrt{3}} & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}}\\
\frac{1}{\sqrt{3}} & 0 & -\frac{2}{\sqrt{6}}\\
\end{bmatrix}.
$$
<!-- eng end -->

##### Exercise 5(a)

已知 $A$ 的行向量彼此互相垂直
且長度皆為 $1$。
以直觀的方式猜測 $\Vol_C(A)$。
真的計算看看你的猜測是否正確。

<!-- eng start -->
We know the columns of $A$ are mutually orthogonal and of length $1$. Guess what is $\Vol_C(A)$ by intuition. Then check if your intuition is correct by definition.
<!-- eng end -->

**Solution:**
Guess $\Vol_C(A)=1$ by intuition since the columns of $A$ are mutually orthogonal and of length $1$ which is similar to a $1\times1\times1$ cube.
We do the column operations:
$$
\rho_1:+(-\sqrt{2})\rho_3 \\
\rho_2:+(-\sqrt{3})\rho_3 \\
\rho_1\leftrightarrow\ \rho_3.
$$
Then we get the matrix below
$$
\begin{bmatrix}
\frac{1}{\sqrt{6}} & 0 & 0 \\
0 & \frac{-2\sqrt{3}}{\sqrt{6}} & 0 \\
0 & 0 & \frac{3{\sqrt{2}}}{\sqrt{6}}
\end{bmatrix}.
$$

Thus,$\Vol_C(A)=\frac{1}{\sqrt{6}}\times\frac{-2\sqrt{3}}{\sqrt{6}}\times\frac{3{\sqrt{2}}}{\sqrt{6}}\times(-1)=1.$
So our guess is correct!

##### Exercise 5(b)

將 $A$ 矩陣的
第一個行向量伸縮為原來的 $3$ 倍，
第二個行向量伸縮為原來的 $4$ 倍，
第三個行向量伸縮為原來的 $5$ 倍，
並得到 $B$ 矩陣。
以直觀的方式猜測 $\Vol_C(B)$。
真的計算看看你的猜測是否正確。

<!-- eng start -->
Construct a new matrix $B$ from $A$ by rescaling the first column by $3$, the second column by $4$, and the third column by $5$. Guess what is $\Vol_C(A)$ by intuition. Then check if your intuition is correct by definition.
<!-- eng end -->
**Solution:**
Guess $\Vol_C(B)=1\times3\times4\times5=60.$
We do the column operations:
$$
\rho_1:+(-\sqrt{2})\rho_3 \\
\rho_2:+(-\sqrt{3})\rho_3 \\
\rho_1\leftrightarrow\ \rho_3.
$$
Then we get the matrix below
$$
\begin{bmatrix}
\frac{5}{\sqrt{6}} & 0 & 0 \\
0 & \frac{-8\sqrt{3}}{\sqrt{6}} & 0 \\
0 & 0 & \frac{9{\sqrt{2}}}{\sqrt{6}}
\end{bmatrix}.
$$
Thus,
$\Vol_C(A)=\frac{5}{\sqrt{6}}\times\frac{-8\sqrt{3}}{\sqrt{6}}\times\frac{9{\sqrt{2}}}{\sqrt{6}}\times(-1)=60.$

So our guess is correct!

##### Exercise 6

積分的概念在於
把許多小方塊（或是其它幾何形狀）的體積累積起來。
當這些小方塊的體積會隨著座標變動的時候則須要乘上一些調整量來確保體積正確。
我們知道笛卡爾座標和極座標轉換時有以下公式

$$
\int f\,dxdy = \int f rdrd\theta.
$$

當 $x = r\cos\theta$ 且 $y = r\sin\theta$ 時，
計算

$$
J = \begin{bmatrix}
\frac{\partial x}{\partial r} & \frac{\partial y}{\partial r} \\
\frac{\partial x}{\partial \theta} & \frac{\partial y}{\partial \theta} \\
\end{bmatrix}
$$

的 $\Vol_C(J)$。
而這個值告訴我們極座標上的一個小方塊
和笛卡爾座標上的一個小方塊
它們的體積的比率為何。

<!-- eng start -->
The spirit of integration is to sum up the volumns of small cubes (or other geometric objects). These cubes will change their volumes by a scalar when some transformation is applied. We knew the formula

$$
\int f\,dxdy = \int f rdrd\theta
$$

for converting a cartesian coordinate system to a polar coordinate system. Let $x = r\cos\theta$ 且 $y = r\sin\theta$. Calculate $\Vol_C(J)$, where

$$
J = \begin{bmatrix}
\frac{\partial x}{\partial r} & \frac{\partial y}{\partial r} \\
\frac{\partial x}{\partial \theta} & \frac{\partial y}{\partial \theta} \\
\end{bmatrix}.
$$

This told us that the ratio between the volumn of a small cube on a polar coordinate system to that on a cartesian coordinate system.
<!-- eng end -->

**[由 :cloud: 提供]**
### Exercise 6 -- answer

After calculating the partial derivatives of $x$ and $y$ with respect to $r$ and $θ$, we have following results, $\displaystyle \frac{\partial x}{\partial r}=\cos\theta,\, \frac{\partial y}{\partial r}=\sin\theta,\, \frac{\partial x}{\partial \theta}=-r\sin\theta,\, \frac{\partial y}{\partial \theta}=r\cos\theta.$
Thus,
$$
J = \begin{bmatrix}
\cos\theta & \sin\theta \\
-r\sin\theta & r\cos\theta \\
\end{bmatrix}.
$$
And the rref of $J$ is :
$$
J = \begin{bmatrix}
\cos\theta & 0 \\
0 & \displaystyle \frac{r}{\cos\theta} \\
\end{bmatrix}.
$$
Therefore $\Vol_C(J)=\cos\theta\times\displaystyle \frac{r}{\cos\theta}=r.$

:::info

collaboration: 2
3 problems: 3

* 2a~c

extra: 4

* 2d, 2e, 3, 4a, 4b

moderator: 1
qc: 1
:::