# 基底

Basis

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_good_matrix

## Main idea

Let $V$ be a subspace in $\mathbb{R}^n$ and $S$ a set of vectors.
The set $S$ is a **spanning set** of $V$ if $V = \vspan(S)$.
The set $S$ is a **basis** of $V$ if
1. $S$ is a spanning set of $V$, and
2. $S$ is independent.

In other words, $S$ is a basis of $V$ if every vector in $V$ can be written as a linear combination of $S$ and the representation is unique.

Let $\mathcal{E}_n = \{ \be_1, \ldots, \be_n \}$ be the columns of $I_n$.
Then $\beta$ is a basis of $\mathbb{R}^n$.
We call $\mathcal{E}_n$ as the **standard basis** of $\mathbb{R}^n$.

Let $S$ and $T$ be two sets of vectors in $\mathbb{R}^n$.
If $T\subseteq\vspan(S)$, then $\vspan(T)\subseteq\vspan(S)$.
Suppose the sets $S$ and $T$ are finite.
Let $A_S$ and $A_T$ be the matrices whose columns are vectors in $S$ and in $T$, respectively.
Let $\left[\begin{array}{c|c} R_S & R_T \end{array}\right]$ be the reduced echelon form of $\left[\begin{array}{c|c} A_S & A_T \end{array}\right]$.
Then the following are equivalent:
1. $T\subseteq\vspan(S)$.
2. A row in $R_T$ is zero whenever the corresponding row in $R_S$ is zero.

Let $A$ be an $m\times n$ matrix.
Then the set of columns of $A$ is a basis of $\Col(A)$ if $\ker(A) = \{\bzero\}$.
In particular, if $m = n$ and $A$ is invertible, then the set of columns of $A$ is a basis of $\mathbb{R}^n$.

## Side stories
- basis of polynomials
- interpolation

## Experiments

##### Exercise 1

執行下方程式碼。
令 $S$ 和 $T$ 為 $A_S$ 和 $A_T$ 的各行向量。
已知 $\left[\begin{array}{c|c} A_S & A_T \end{array}\right]$ 的最簡階梯形式矩陣為 $\left[\begin{array}{c|c} R_S & R_T \end{array}\right]$﹐
而 $\left[\begin{array}{c|c} A_T & A_S \end{array}\right]$ 的最簡階梯形式矩陣為 $\left[\begin{array}{c|c} Q_T & Q_S \end{array}\right]$。

<!-- eng start -->
Run the code below. Let $S$ and $T$ be the columns of $A_S$ and $A_T$. Suppose $\left[\begin{array}{c|c} R_S & R_T \end{array}\right]$ is the reduced echelon form of $\left[\begin{array}{c|c} A_S & A_T \end{array}\right]$, while $\left[\begin{array}{c|c} Q_T & Q_S \end{array}\right]$ is the reduced echelon form of $\left[\begin{array}{c|c} A_T & A_S \end{array}\right]$.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False
m,n,r = 5,4,4
A = random_good_matrix(m,n,r)
ES = random_good_matrix(3,3,3)
ET = random_good_matrix(3,3,3)
SinT = choice([True, False])
TinS = choice([True, False])
if SinT and TinS:
    AS,AT = A[:,:3],A[:,:3]
if SinT and not TinS:
    AS,AT = A[:,[0,1,1]],A[:,:3]
if not SinT and TinS:
    AS,AT = A[:,:3],A[:,[0,1,1]]
if not SinT and not TinS:
    AS,AT = A[:,:3],A[:,1:]
AS = AS * ES
AT = AT * ET

ST = AS.augment(AT, subdivide=True)
RST = ST.rref()
TS = AT.augment(AS, subdivide=True)
QTS = TS.rref()

print("[ A_S | A_T ] =")
show(ST)
print("[ R_S | R_T ] =")
show(RST)
print("[ Q_T | Q_S ] =")
show(QTS)

if print_ans:
    print("span(S) in span(T)?", SinT)
    print("span(T) in span(S)?", TinS)

By setting `seed = 0` , we get
$\left[\begin{array}{c|c}
A_S & A_T\end{array}\right]
= \left[\begin{array}{ccc|ccc}
42 & -71 & 244 & 49 & 72 & 8 \\
-159 & 270 & 919 & -191 & -279 & -35 \\
610 & -1035 & -3529 & 729 & 1066 & 131 \\
-2590 & 4396 & 14978 & -3102 & -4534 & -562 \\
6356 & -10789 & -36753 & 7617 & 11132 &1383
\end{array}\right],$

$\left[\begin{array}{c|c}
R_S & R_T \end{array}\right]
= \left[\begin{array}{ccc|ccc}
1 & 0 & 0 & 43 & 67 & 6 \\
0 & 1 & 0 & 11 & 18 & 0 \\
0 & 0 & 1 & 4 & 6 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{array}\right],$
and
$\left[\begin{array}{c|c}
Q_T & Q_S \end{array}\right]
= \left[\begin{array}{ccc|ccc}
1 & 0 & 0 & 18 & -31 & -108 \\
0 & 1 & 0 & -11 & 19 & 66 \\
0 & 0 & 1 & -6 & 10 & 37 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{array}\right].$

---

##### Exercise 1(a)

問 $\vspan(S)\subseteq\vspan(T)$？

<!-- eng start -->
Is $\vspan(S)\subseteq\vspan(T)$?
<!-- eng end -->

:::warning

- [x] Split the sentence or add some conjunctions: Every vector in $S$ is in the $\operatorname{Col}(A_T),$ we know that $\operatorname{Col}(A_T)=\vspan(T),$
so $S\subseteq\vspan(T),$ then know that $\vspan(S)\subseteq\vspan(T).$ --> Every vector in $S$ is in the $\operatorname{Col}(A_T),$ ==so== we know that $\operatorname{Col}(A_T)=\vspan(T).$ ==period here==
~~so~~ ==Thus,== $S\subseteq\vspan(T),$ ~~then~~ ==and== know that $\vspan(S)\subseteq\vspan(T).$
:::

##### <font color="#f00">**Answer:**</font>

The reduced row echelon form of $\left[\begin{array}{c|c} A_T & A_S \end{array}\right]$ is $\left[\begin{array}{ccc|ccc}
1 & 0 & 0 & 18 & -31 & -108 \\
0 & 1 & 0 & -11 & 19 & 66 \\
0 & 0 & 1 & -6 & 10 & 37 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{array}\right].$
We can know
$$
A_T\begin{bmatrix}
18 & -31 & -108\\
-11 & 19 & 66\\
-6 & 10 & 37\\
\end{bmatrix}=A_S.
$$
Every vector in $S$ is in the $\operatorname{Col}(A_T),$ and we know that $\operatorname{Col}(A_T)=\vspan(T)$.
Thus, $S\subseteq\vspan(T),$ and we know that $\vspan(S)\subseteq\vspan(T).$

---

:::warning

- [x] same as 1(a)
:::

##### Exercise 1(b)

問 $\vspan(T)\subseteq\vspan(S)$？

<!-- eng start -->
Is $\vspan(T)\subseteq\vspan(S)$?
<!-- eng end -->

##### <font color="#f00">**Answer:**</font>
The reduced row echelon form of $\left[\begin{array}
{c|c} A_S & A_T \end{array}\right]$ is
$\left[\begin{array}{ccc|ccc}
1 & 0 & 0 & 43 & 67\ & 6 \\
0 & 1 & 0 & 11 & 18 & 0 \\
0 & 0 & 1 & 4 & 6 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{array}\right].$
We can know
$$A_S\begin{bmatrix}
43 & 67 & 6\\
11 & 18 & 0\\
4 & 6 & 1\\
\end{bmatrix}=A_T.
$$
Every vector in $T$ is in the $\operatorname{Col}
(A_S),$ and we know that $\operatorname{Col}
(A_S)=\vspan(S).$
Thus, $T\subseteq\vspan(S),$ and we know that
$\vspan(T)\subseteq\vspan(S).$

---

## Exercises

##### Exercise 2(a)

執行以下程式碼。
其中 $R$ 是 $A$ 的最簡階梯形式矩陣。
說明 $A$ 的行向量所成的集合
是 $A$ 的行空間的基底。

<!-- eng start -->
Run the code below. Suppose $R$ is the reduced echelon form of $A$. Explain why the columns of $A$ form a basis of the column space of $A$.
<!-- eng end -->

### code
set_random_seed(0)
# print_ans = False
m,n,r = 5,3,3
A = random_good_matrix(m,n,r)
print("A =")
show(A)
R = A.rref()
print("R =")
show(R)

:::warning

- [x] Wrong statement: By definition, we know that every vector in ==$\Col(A)$== can be written as a linear combination of ==columns of $A$==
:::

##### <font color="#f00">**Answer:**</font>
By setting `seed = 0` , we get :
$$A = \left[\begin{array}{ccc}
1 & 3 & 5 \\
5 & -14 & -30 \\
-15 & -42 & -89 \\
28 & 79 & 162 \\
-13 & -37 & -73 \
\end{array}\right],
\,R = \left[\begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 0 \\
0 & 0 & 0 \\
\end{array} \right].
$$

We know that columns of $A$ are linearly independent since $\ker(A)=\{\bzero\}$ by checking the reduced row echelon form of $A$.

By definition, we know that every vector in $\Col(A)$ can be written as a linear combination of cloumns of $A$ and the representation is unique, so the set of all the column vectors in $A$ is a basis of $\Col(A)$.

---
##### Exercise 2(b)

執行以下程式碼。
其中 $R$ 是 $A$ 的最簡階梯形式矩陣。
說明 $A$ 的行向量所成的集合
是 $\mathbb{R}^4$ 的基底。

<!-- eng start -->
Run the code below. Suppose $R$ is the reduced echelon form of $A$. Explain why the columns of $A$ form a basis of $\mathbb{R}^4$.
<!-- eng end -->

### code
set_random_seed(0)
# print_ans = False
m,n,r = 4,4,4
A = random_good_matrix(m,n,r)
print("A =")
show(A)
R = A.rref()
print("R =")
show(R)

##### <font color="#f00">**Answer:**</font>

---
##### Exercise 2(c)

令

$$
\beta = \left\{
\begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix},
\begin{bmatrix} 0 \\ 1 \\ -1 \end{bmatrix}
\right\}
$$

且

$$
V = \{ \bx\in\mathbb{R}^3 : \inp{\bone}{\bx} = 0 \}.
$$

其中 $\bone$ 是 $\mathbb{R}^3$ 中的全 $1$ 向量。
證明 $\beta$ 是 $V$ 的一組基底。

<!-- eng start -->
Let

$$
\beta = \left\{
\begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix},
\begin{bmatrix} 0 \\ 1 \\ -1 \end{bmatrix}
\right\}
$$

and

$$
V = \{ \bx\in\mathbb{R}^3 : \inp{\bone}{\bx} = 0 \}.
$$

Here $\bone$ is the all-ones vector in $\mathbb{R}^3$. Show that $\beta$ is a basis of $V$.
<!-- eng end -->

##### <font color="#f00">**Answer:**</font>
---

##### Exercise 3

以下的例子說明了多項式也有類似地基底的性質：
每一個多項式都可以被某些多項式組合出來、
而且「表示法唯一」。

<!-- eng start -->
The following examples demonstrate that polynomials have the similar behavior as the basis: Every polynomial can represented as the linear combination of some polynomials, and the representation is unique.
<!-- eng end -->

##### Exercise 3(a)

證明每一個二次多項式 $f(x)$ 都可以寫成 $c_0 + c_1(x-1) + c_2(x-1)^2$ 的樣子﹐
而且 $c_0,c_1,c_2$ 的選擇唯一。

<!-- eng start -->
Show that every polynomial $f(x)$ of degree at most $2$ can be written as $c_0 + c_1(x-1) + c_2(x-1)^2$, and the choice of $c_0, c_1, c_2$ is unqiue.
<!-- eng end -->

:::warning

- [x] Nice! But $c_0,c_1,c_2$ are coefficients but not vectors, so the sentence
Write $c_0$, $c_1$, and $c_2$ as $\begin{bmatrix}0\\0\\1\end{bmatrix},\begin{bmatrix}0\\1\\-1\end{bmatrix},\begin{bmatrix}1\\-2\\1\end{bmatrix}.$
does not make sense. Try the following:

Expand the polynomial. Then we can get

$$
\begin{aligned}
& c_0 (0x^2 + 0x + 1) + \\
& c_1(0x^2 + x - 1) + \\
& c_2(x^2 - 2x + 1).
\end{aligned}
$$

By recording the coefficients of $x^2$, $x$, and $1$ as a vector, we get three vectors $\begin{bmatrix}0\\0\\1\end{bmatrix},\begin{bmatrix}0\\1\\-1\end{bmatrix},\begin{bmatrix}1\\-2\\1\end{bmatrix}$ controled by $c_0$, $c_1$, and $c_2$, respectively.

- [x] Since $A$ is nonsingular, for any $\bb\in\mathbb{R}^3$, the equation $A\bx = \bb$ has a unique solution. Equivalently, for any polynomial $f$ of degree at most $2$, the equality $c_0 + c_1(x-1) + c_2(x-1)^2 = f(x)$ has a unique solution.
- [x] The $\ker(A)=\{0\}$, we know that the $c_0$, $c_1$, and $c_2$ are linear independent. --> Since $\ker(A)=\{0\}$, we know that the columns of $A$ are linear independent.
:::

##### <font color="#f00">**Answer:**</font>
Expand the polynomial. Then we can get
$$
\begin{aligned}
& c_0 (0x^2 + 0x + 1) + \\
& c_1(0x^2 + x - 1) + \\
& c_2(x^2 - 2x + 1).
\end{aligned}
$$

By recording the coefficients of $x^2$, $x$, and $1$ as a vector, we get three vectors $\begin{bmatrix}0\\0\\1\end{bmatrix},\begin{bmatrix}0\\1\\-1\end{bmatrix},\begin{bmatrix}1\\-2\\1\end{bmatrix}$ controled by $c_0$, $c_1$, and $c_2$, respectively.
Let $A$ be the matrix
$$\begin{bmatrix}
0 & 0 & 1\\
0 & 1 & -2\\
1 & -1 & 1\\
\end{bmatrix}.
$$

Since $\ker(A)=\{\bzero\}$, we know that the columns of $A$ are linear independent.
Since $A$ is nonsingular, for any $\bb\in\mathbb{R}^3$, the equation $A\bx = \bb$ has a unique solution. Equivalently, for any polynomial $f$ of degree at most $2$, the equality $c_0 + c_1(x-1) + c_2(x-1)^2 = f(x)$ has a unique solution.

---

##### Exercise 3(b)

令

$$
\begin{aligned}
f_1(x) &= \frac{(x-2)(x-3)}{(1-2)(1-3)}, \\
f_2(x) &= \frac{(x-1)(x-3)}{(2-1)(2-3)}, \\
f_3(x) &= \frac{(x-1)(x-2)}{(3-1)(3-2)}. \\
\end{aligned}
$$

證明每一個二次多項式 $f(x)$ 都可以寫成 $c_1f_1(x) + c_2f_2(x) + c_3f_3(x)$ 的樣子﹐
而且 $c_1,c_2,c_3$ 的選擇唯一。

<!-- eng start -->
Let

$$
\begin{aligned}
f_1(x) &= \frac{(x-2)(x-3)}{(1-2)(1-3)}, \\
f_2(x) &= \frac{(x-1)(x-3)}{(2-1)(2-3)}, \\
f_3(x) &= \frac{(x-1)(x-2)}{(3-1)(3-2)}. \\
\end{aligned}
$$

Show that every polynomial $f(x)$ of degree at most $2$ can be written as $c_1f_1(x) + c_2f_2(x) + c_3f_3(x)$, and the choice of $c_1, c_2, c_3$ is unqiue.
<!-- eng end -->

:::warning

- [x] When $x=1$, we have $f_1(x)=1, f_2(x)=0, f_3(x)=0.$
When $x=2$, we have $f_1(x)=0, f_2(x)=1, f_3(x)=0$.
When $x=3$, we have $f_1(x)=0, f_2(x)=0, f_3(x)=1.$
- [x] It is not clear yet what is the meaning of independence. For this problem, you just have to solve $c_1 = f(1)$, $c_2 = f(2)$, and $c_3 = f(3)$.
:::

##### <font color="#f00">**Answer:**</font>
From the equation above, we found some properties by setting $x=1, 2, 3.$
When $x=1$, we have $f_1(x)=1, f_2(x)=0, f_3(x)=0,$
When $x=2$, we have $f_1(x)=0, f_2(x)=1, f_3(x)=0,$
When $x=3$, we have $f_1(x)=0, f_2(x)=0, f_3(x)=1.$

In order to prove that there are unique $c_1, c_2, c_3$ in real numbers such that $f(x) = c_1f_1(x) + c_2f_2(x) + c_3f_3(x)$, we can solve $c_1 = f(1)$, $c_2 = f(2)$, and $c_3 = f(3)$, so we know that $f_1(x), f_2(x), f_3(x)$ are independent and they are a basis of all polynomials $f(x)$ of degree at most $2$.

---
##### Exercise 4

執行以下程式碼。
其中 $B$ 為 $A$ 的反矩陣。
令 $S = \{\bu_1,\bu_2,\bu_3\}$ 為 $A$ 的各行向量。
因為 $A$ 可逆﹐所以 $S$ 為 $\mathbb{R}^3$ 的一組基底。
也就是說﹐每一個 $\mathbb{R}^3$ 中的向量都可以用 $S$ 中的向量組合出來﹐而且組合方法唯一。

<!-- eng start -->
Run the code below. Let $B$ be the inverse of $A$ and $S = \{\bu_1,\bu_2,\bu_3\}$ the columns of $A$. Since $A$ is invertible, so $S$ is a basis of $\mathbb{R}^3$. That is, every vector in $\mathbb{R}^3$ can be written as a linear combination of $S$, and the representation is unique.
<!-- eng end -->

### code
set_random_seed(0)
A = random_good_matrix(3,3,3)
B = A.inverse()
print("A =")
show(A)
print("B =")
show(B)

令`set_random_seed(0)`得

$A = \begin{bmatrix}
1 & 3 & 5\\
-5 & -14 & -30\\
-15 & -42 & -89
\end{bmatrix},B = \begin{bmatrix}
-14 & 57 & -20\\
5 & -14 & 5\\
0 & -3 & 1
\end{bmatrix}$.

##### Exercise 4(a)

令 $\be_1,\be_2,\be_3$ 分別為 $I_3$ 的三個行向量。
對每一個 $i = 1,2,3$﹐求出 $\be_i$ 寫成 $S$ 的線性組合的表示法。

<!-- eng start -->
Let $\be_1, \be_2, \be_3$ be the columns of $I_3$. For each $i = 1, 2, 3$, write $\be_i$ as a linear combination of $S$.
<!-- eng end -->

:::warning

- [x] So ==space==

Otherwise, it is nice.
:::

##### <font color="#f00">**Answer:**</font>
Because $B$ is the inverse of $A$, so

$$
\begin{aligned}
AB&=A\begin{bmatrix}
| & | & |\\
{\bf b}_1 & {\bf b}_2 & {\bf b}_3\\
| & | & |\\
\end{bmatrix}\\\\
&=\begin{bmatrix}
| & | & |\\
{\bf e}_1 & {\bf e}_2 & {\bf e}_3\\
| & | & |\\
\end{bmatrix}\\\\
&=I_3.
\end{aligned}
$$

So $A{\bf b}_i = {\bf e}_i$

$$
\begin{cases}
{\bf e}_1 = -14{\bf u}_1 + 5{\bf u}_2,\\
{\bf e}_2 = 57{\bf u}_1 - 14{\bf u}_2 - 3{\bf u}_3,\\
{\bf e}_3 = -20{\bf u}_1 + 5{\bf u}_2 + {\bf u}_3.
\end{cases}
$$

---

##### Exercise 4(b)

令 $\bb = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$。
求出 $\bb$ 寫成 $S$ 的線性組合的表示法。

<!-- eng start -->
Let $\bb = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$. Write $\bb$ as a linear combination of $S$.
<!-- eng end -->

##### <font color="#f00">**Answer:**</font>

$$
\begin{aligned}
{\bf b}
&= {\bf e}_1 + {\bf e}_2 + {\bf e}_3\\
&= 23{\bf u}_1 - 4{\bf u}_2 - 2{\bf u}_3。
\end{aligned}
$$

:::info

collaboration: 1
4 problem: 4

extra: 0.5

moderator: 1
quality control: 1
:::