Projection and reflection
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
Let
$$ A = \begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & ~ & \vdots \\
a_{m1} & \cdots & a_{mn} \\
\end{bmatrix} \text{ and }
B = \begin{bmatrix}
b_{11} & \cdots & b_{1\ell} \\
\vdots & ~ & \vdots \\
b_{n1} & \cdots & b_{n\ell} \\
\end{bmatrix}$$
be $m\times n$ and $n\times \ell$ matrices, respectively.
Then the $ij$-entry of $AB$ is
$$(AB)_{ij} = \sum_{k = 1}^n a_{ik}b_{kj}.$$
Let $A$ be an $m\times n$ matrix.
The transpose of $A$ is the $n\times m$ matrix $A\trans$ whose $ij$-entry is the $ji$-entry of $A$.
The $n\times n$ identity matrix is the matrix whose diagonal entries are one and other entries are zero, usually denoted as $I_n$.
The $m\times n$ zero matrix is the matrix whose entries are zero, usually denoted as $O_{m,n}$.
If $A$ is an $n\times n$ matrix and there is a matrix $B$ such that $AB = BA = I_n$,
then $B$ is called the inverse of $A$, denoted as $A^{-1} = B$.
A matrix with an inverse is invertible.
Suppose $A$ is an $n\times k$ matrix with $\ker(A) = \{\bzero\}$.
Then every vector $\bb\in\mathbb{R}^n$ can be written as
$$\bb = \bw + \bh$$
where $\bw\in\Col(A)$ and $\bh\in\Col(A)^\perp$.
Moreover,
$$\begin{aligned}
\bw &= A(A\trans A)^{-1}A\trans \bb, \\
\bh &= \bb - \bw.
\end{aligned}$$
We say $\bw$ is the projection of $\bb$ onto the subspace $\Col(A)$, and
$\bw - \bh$ the reflection of $\bb$ along the subspace $\Col(A)$.
Both action can be done by matrices.
That is,
$$\begin{aligned}
\bw &= A(A\trans A)^{-1}A\trans \bb, \\
\bw - \bh &= 2\bw - \bb = (2A(A\trans A)^{-1}A\trans - I_n)\bb.
\end{aligned}$$
執行下方程式碼。
依照步驟求出 $\bb$ 在 $\Col(A)$ 上的投影。
Run the code below. Use the given instructions to find the projection of $\bb$ onto $\Col(A)$.
### code
set_random_seed(0)
print_ans = False
while True:
A = matrix(2, random_int_list(8)).transpose()
if (A.transpose() * A).is_invertible():
break
b = vector(random_int_list(4))
print("A =")
print(A)
print("b =", b)
if print_ans:
AT = A.transpose()
ATA = AT * A
w = A * ATA.inverse() * AT * b
print("The projection is %s."%w)
假設 $\bb = \bw + \bh$ 使得
$\bw\in\Col(A)$(也就是有某一個 $\bv$ 使得 $\bw = A\bv$)、
$\bh\in\Col(A)^\perp = \Row(A\trans)^\perp = \ker(A\trans)$(也就是 $A\trans\bh = \bzero$)。
將 $\bb = \bw + \bh$ 兩邊前乘 $A\trans$﹐
並用 $A$、$\bb$、和 $\bv$ 表示出來。
Assume $\bb = \bw + \bh$ such that $\bw\in\Col(A)$ (meaning $\bw = A\bv$ for some $\bv$) and $\bh\in\Col(A)^\perp = \Row(A\trans)^\perp = \ker(A\trans)$ (meaning $A\trans\bh = \bzero$).
Multiply the both sides of $\bb = \bw + \bh$ by $A\trans$. Then rewrite the equation by $A$, $\bb$, and $\bv$.
將 $A$ 和 $\bb$ 的數字代入並解方程式求出 $\bv$。
(如果 $A\trans A$ 可逆﹐
則可以把上一題的式子寫成 $\bv = (A\trans A)^{-1} A\trans \bb$。)
Plug in the numbers for $A$ and $\bb$ to find $\bv$.
(Note that if $A\trans A$ is invertible, then the equation from the previous problem can be written as $\bv = (A\trans A)^{-1} A\trans \bb$.)
因此我們知道
$$ \begin{aligned} \bw &= A\bv, \\ \bh &= \bb - \bw. \end{aligned} $$以題目給的 $A$ 和 $\bb$ 將 $\bw$ 和 $\bh$ 求出來﹐
並確認 $A\trans\bh = \bzero$。
Therefore, we know
$$ \begin{aligned} \bw &= A\bv, \\ \bh &= \bb - \bw. \end{aligned} $$Use the $A$ and $\bb$ given in the problem to find $\bw$ and $\bh$. Then verify $A\trans\bh = \bzero$.
若 $\bx$ 和 $\by$ 為 $\mathbb{R}^n$ 中的兩向量。
驗證 $\inp{\bx}{\by} = \by\trans\bx$。
(這裡的右式把 $\bx$ 和 $\by$ 都當成 $n\times 1$ 的矩陣
而算出來的 $1\times 1$ 的矩陣 $\by\trans\bx$ 被當成一個數字。)
Let $\bx$ and $\by$ be vectors in $\mathbb{R}^n$. Verify $\inp{\bx}{\by} = \by\trans\bx$. (Here on the right hand side of the equation, we view $\bx$ and $\by$ as $n\times 1$ matrices, while the output $\by\trans\bx$ is an $1\times 1$ matrix and is viewed as a number.)
若 $A$ 和 $B$ 分別為 $m\times n$ 和 $n\times \ell$ 的兩矩陣。
驗證 $(AB)\trans = B\trans A\trans$。
Let $A$ and $B$ be $m\times n$ and $n\times m$ matrices, respectively. Verify $(AB)\trans = B\trans A\trans$.
驗證 $\inp{A\bx}{\by} = \by\trans A\bx = \inp{\bx}{A\trans\by}$。
Verify $\inp{A\bx}{\by} = \by\trans A\bx = \inp{\bx}{A\trans\by}$.
證明 $\ker(A) = \ker(A\trans A)$。
因為 $A\trans A$ 是一個方陣,
後面會證明一個方陣 $M$ 可逆的等價條件就是 $\ker(M) = \{\bzero\}$。
因此 $\ker(A) = \{\bzero\}$ 足以保證 $A\trans A$ 可逆。
另一方面,
如果 $\ker(A) \neq \{\bzero\}$,
表示 $A$ 中的行向量有一些可以去掉並不會影響到行空間。
重覆這個步驟直到沒有任何多餘的行向量時
(這時行空間都還是同一個)
就保證有 $\ker(A) = \{\bzero\}$。
(參考【矩陣的行向量】中的練習。)
Prove $\ker(A) = \ker(A\trans A)$.
We will learn that a square matrix $M$ with $\ker(M) = \{\bzero\}$ is always invertible. Since $A\trans A$ is a square matrix, $\ker(A) = \{\bzero\}$ implies $A\trans A$ is invertible.
On the other hand, if $\ker(A) \neq \{\bzero\}$, then there are some redundant columns in $A$, whose removal does not change the column space. Keep removing these volumns while preserving the column space until there is no more redundant column. Therefore, we may always assume $\ker(A) = \{\bzero\}$. (See 103-4.)
想像矩陣乘法就是一個動作(像是投影、或是鏡射)
若 $A$ 是一個投影矩陣、
$\bb$ 是一個向量。
猜看看 $A^2\bb$ 會是什麼?
猜看看 $A^2$ 會是什麼?
(下方程式碼中的矩陣是一個投影矩陣。
可以試試看。)
Imagine that multiplying a matrix is like applying an action, e.g., projection or reflection, to a vector. Let $A$ is a projection matrix and $\bb$ a vector. Guess what is $A^2\bb$ and what is $A^2$? Provide your reasons. (You may run some examples by the code below.)
### code
set_random_seed(0)
a = vector(random_int_list(3))
A = a.outer_product(a) / a.norm()**2
b = vector(random_int_list(3))
print("A =")
show(A)
print("b =", b)
想像矩陣乘法就是一個動作(像是投影、或是鏡射)
若 $A$ 是一個鏡射矩陣、
$\bb$ 是一個向量。
猜看看 $A^2\bb$ 會是什麼?
猜看看 $A^2$ 會是什麼?
(下方程式碼中的矩陣是一個投影矩陣。
可以試試看。)
Imagine that multiplying a matrix is like applying an action, e.g., projection or reflection, to a vector. Let $A$ is a reflection matrix and $\bb$ a vector. Guess what is $A^2\bb$ and what is $A^2$? Provide your reasons. (You may run some examples by the code below.)
### code
set_random_seed(0)
a = vector(random_int_list(3))
A = 2*a.outer_product(a) / a.norm()**2 - identity_matrix(3)
b = vector(random_int_list(3))
print("A =")
show(A)
print("b =", b)
令 $A$、$B$、$C$ 為矩陣
$\bx$ 和 $\by$ 為向量、$k$ 為純量。
驗證以下的矩陣運算等式。
Let $A$, $B$, and $C$ be matrices. Let $\bx$ and $\by$ be vectors. Let $k$ be a scalar. Verify the following identities.
若 $A$ 和 $B$ 皆為可逆矩陣。
則 $(AB)^{-1} = B^{-1}A^{-1}$。
Show that if both $A$ and $B$ are invertible, then $(AB)^{-1} = B^{-1}A^{-1}$.
定義一個方陣 $M$ 的跡數(trace)為其對角線上的所有元素相加,記作 $\tr(M)$。
則 $\tr(A +B) = \tr(A) + \tr(B)$。
Define the trace of a square matrix $M$ as the sum of all its diagonal entries, denoted by $\tr(M)$. Show that $\tr(A +B) = \tr(A) + \tr(B)$.
若 $A$ 和 $B$ 為 $2\times 2$ 的方陣。
則 $\det(AB) = \det(A) \cdot \det(B)$。
(實際上 $n\times n$ 都對,但我們還沒學到 $n\times n$ 方陣的行列式值怎麼算。)
Let $A$ and $B$ be $2\times 2$ matrices. Show that $\det(AB) = \det(A) \cdot \det(B)$.
(In fact, this identity is true for any $n\times n$ matrices. However, we have not learned what is the determinant of an $n\times n$ matrix.)