# 線性獨立

Linear independence

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, random_int_list, kernel_matrix

## Main idea

Let $S = \{\bu_1,\ldots,\bu_k\}$ be a set of finite many vectors.
We say $S$ is **linearly independent** if the only coefficients $c_1,\ldots, c_k\in\mathbb{R}$ satisfying

$$
c_1\bu_1 + \cdots + c_k\bu_k = \bzero
$$

is $c_1 = \cdots = c_k = 0$.
(A infinite set of vectors is linearly independent if any finite subsut of it is linearly independent.)

The following are equivalent:

1. $S$ is linearly independent.
2. For any vector $\bu\in S$, $\bu\notin\vspan(S\setminus\{\bu\})$.
3. For any vector $\bu\in S$, $\vspan(S\setminus\{\bu\})\subsetneq\vspan(S)$.

Therefore, intuitively, $S$ is linearly independent means every vector in it is important.

There are other equivalent conditions that is easier to check.
Let $S$ be a set of vectors and $A$ the matrix whose columns are vectors in $S$.
The following are equivalent:

1. $S$ is linearly independent.
2. The representation of any linear combination of $S$ is unique.
That is, if $\bb = c_1\bu_1 + \cdots + c_k\bu_k = d_1\bu_1 + \cdots + d_k\bu_k$, then $c_1 = d_1$, $\ldots$, and $c_k = d_k$.
3. For any $\bb\in\Col(A)$, the solution to $A\bx = \bb$ is unique.
4. $\ker(A) = \{\bzero\}$.

## Side stories

- unique representation of polynomials
- interpolation

## Experiments

##### Exercise 1

執行下方程式碼。
矩陣 $\left[\begin{array}{c|c} R & \br \end{array}\right]$ 是 $\left[\begin{array}{c|c} A & \bb \end{array}\right]$ 的最簡階梯形式矩陣。
令 $\bu_1,\ldots,\bu_5$ 為 $A$ 的各行向量。

<!-- eng start -->
Run the code below. Let $\left[\begin{array}{c|c} R & \br \end{array}\right]$ be the reduced echelon form of $\left[\begin{array}{c|c} A & \bb \end{array}\right]$. Let $\bu_1,\ldots,\bu_5$ be the columns of $A$.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False
m,n,r = 3,5,2
A = random_good_matrix(m,n,r)
v = vector(random_int_list(5))
b = A * v
Ab = A.augment(b, subdivide=True)
Rr = Ab.rref()

print("[ A | b ] =")
show(Ab)
print("[ R | r ] =")
show(Rr)

if print_ans:
    c = kernel_matrix(A).transpose()[0]
    print("{} u1 + {} u2 + {} u3 + {} u4 + {} u5 = 0".format(*c))
    print("b = {} u1 + {} u2 + {} u3 + {} u4 + {} u5".format(*v))
    print("b = {} u1 + {} u2 + {} u3 + {} u4 + {} u5".format(*(v+c)))
    for i in range(5):
        if c[i] != 0:
            first = i
            break
    print("u%s = -( "%(i+1) + 
          " + ".join("%s u%s"%(c[i]/c[first], i+1) for i in range(5) if i != first) + " )")

---

:::warning

- [x] Use boldface for vectors, e.g., $b$ --> $\bb$ and $r$ --> $\br$
:::

##### Exercise 1 -- answer here
Let `seed = 2`, we get

$$ \left[\begin{array}{c|c} A & \bb \end{array}\right] = \left[\begin{array}{ccccc|c}
1 & -4 & -3 & 1 & 4 & 14 \\
-1 & 4 & 3 & -1 & -3 & -12 \\
-8 & 32 & 24 & -8 & -27 & -102
\end{array}\right].
$$

$$ \left[\begin{array}{c|c} R & \br \end{array}\right] = \left[\begin{array}{ccccc|c}
1 & -4 & -3 & 1 & 0 & 6 \\
0 & 0 & 0 & 0 & 1 & 2 \\
0 & 0 & 0 & 0 & 0 & 0
\end{array}\right].
$$

---
##### Exercise 1(a)

找一群不是全為 $0$ 的數字 $c_1,\ldots,c_5$﹐
使得 $c_1\bu_1 + \cdots + c_5\bu_5 = \bzero$。

<!-- eng start -->
Find some numbers $c_1, \ldots, c_5$ that are not all zeros such that $c_1\bu_1 + \cdots + c_5\bu_5 = \bzero$.
<!-- eng end -->

---

:::warning
Grammar error:

- [x] Let ... . Thus, they ... .

Please add some reasons. For example:
It is enough to find some $c_1,\ldots, c_5$ such that

$$
R ? = \bzero.
$$

:::

##### Exercise 1(a) -- answer here

It is enough to find some $c_1,\ldots, c_5$ such that
$$
R \begin{bmatrix}
c_1 \\
c_2 \\
c_3 \\
c_4 \\
c_5 \\
\end{bmatrix} = \bzero.
$$

Let $c_1 = 5,c_2 = -3,c_3 = 4,c_4= -5, c_5 = 0$.

Thus, they satisfy $5{\bf u}_1 -3{\bf u}_2 + 4{\bf u}_3 -5{\bf u}_4 + 0{\bf u}_5 = {\bf 0}$.

---
##### Exercise 1(b)

已知 $\bb \in \Col(A)$。
找兩群相對應數字不完全一樣的數字 $c_1,\ldots,c_5$ 和 $d_1,\ldots,d_5$﹐
使得 $c_1\bu_1 + \cdots + c_5\bu_5 = d_1\bu_1 + \cdots + d_5\bu_5$。

<!-- eng start -->
Suppose $\bb\in\Col(A)$. Find two different sets of numbers $c_1,\ldots,c_5$ and $d_1,\ldots,d_5$ such that $c_1\bu_1 + \cdots + c_5\bu_5 = d_1\bu_1 + \cdots + d_5\bu_5$.

---

:::warning
:thumbsup: Mathematics is correct.
:x: Please add some reasons. For example, we already know that $... = \bzero$. For any linear combination, say $\bb = 7\bu_1 + (-3)\bu_2 + ...$, we also have

$$
\bb = \bb + \bzero = ... .
$$
:::

##### Exercise 1(b) -- answer here

Suppose ${\bf b} = c_1{\bf u}_1 + \cdots + c_5{\bf u}_5 = d_1{\bf u}_1 + \cdots + d_5{\bf u}_5$.
It is enough to find some $c_1,\ldots, c_5$ and $d_1,\ldots, d_5$ such that
$$
R \begin{bmatrix}
c_1 \\
c_2 \\
c_3 \\
c_4 \\
c_5 \\
\end{bmatrix} =
R \begin{bmatrix}
d_1 \\
d_2 \\
d_3 \\
d_4 \\
d_5 \\
\end{bmatrix} =
\bb.
$$
We find that
${\bf b}= 7{\bf u}_1 + (-3){\bf u}_2 + 4{\bf u}_3 + (-1){\bf u}_4 + 2{\bf u}_5 = 8{\bf u}_1 + 6{\bf u}_2 + (-8){\bf u}_3 + (-2){\bf u}_4 + 2{\bf u}_5$.

---
##### Exercise 1(c)

將 $A$ 的其中一個行向量寫成其它行向量的線性組合。

<!-- eng start -->
Find a column of $A$ that can be written as a linear combination of other columns.
<!-- eng end -->

---

:::warning

Correct. In fact, you can read this relation from $R$.

- [x] ${\bf u}_2$=(-4)${\bf u}_1$ --> $\bu_2 =(-4) \bu_1$ (read the source code)
:::

##### Exercise 1(c) -- answer here
By observing the matrix $R$ ,
we can find that
$$
{\bf u}_2=(-4){\bf u}_1.
$$

---
## Exercises

##### Exercise 2

執行以下程式碼。
令 $S = \{ \bu_1, \bu_2, \bu_3 \}$ 為矩陣 $A$ 的各行向量。
問 $S$ 是否線性獨立。
若是，將 $\bb$ 寫成 $S$ 的線性組合。
若否，找到一個 $S$ 中的向量將其寫成其它向量的線性組合。

<!-- eng start -->
Run the code below. Let $S = \{ \bu_1, \bu_2, \bu_3 \}$ be the columns of $A$. Is $S$ linearely independent? If yes, write $\bb$ as a linear combination of $S$. If not, find a vector in $S$ that can be written as a linear combination of other vectors in $S$.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False
ind = choice([True, False])
m,n,r = 5,3,3 if ind else 2
A = random_good_matrix(m,n,r)
print("A =")
show(A)
v = vector(random_int_list(3))
b = A * v
print("b =", b)

if print_ans:
    print("Linearly independent?", ind)
    if ind:
        print("b = " + " + ".join("%s u%s"%(v[i], i+1) for i in range(3)))
    else:
        c = kernel_matrix(A).transpose()[0]
        for i in range(3):
            if c[i] != 0:
                first = i
                break
        print("u%s = -( "%(i+1) + 
              " + ".join("%s u%s"%(c[i]/c[first], i+1) for i in range(3) if i != first) + " )")

:::warning

Mathematics:

$$
\left[\begin{array}{c|c} A & \bb \end{array}\right] = \left[\begin{array}{ccc|c}
1 & 0 & 0 & -3 \\
0 & 1 & 0 & -3 \\
0 & 0 & 1 & -2 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{array}\right]
$$

is not true. The equal sign $=$ should be an arrow $\rightarrow$.

Typesetting:

- [x] $Col(A)$ --> $\Col(A)$, $Ker(A) = 0$ --> $\ker(A) = \{\bzero\}$ (read source code)
- [x] Check if you miss some periods.
- [x] Use boldface for vectors, e.g., $0$ --> $\bzero$ if it is a zero vector
:::

##### Exercise 2 - Solution by Kevin
From the result of the code,

$$
A=\begin{bmatrix}
1 & -5 & 0\\
-3 & 16 & 3\\
12 & -63 & -8\\
-50 & 264 & 38\\
-28 & 147 & 20\\
\end{bmatrix}
$$

and
$$
\bb=(12, -45, 169, -718, -397).
$$

As
"$S$ is linearly independent"
is equivalent to
"$\ker(A) = \{\bzero\}$".

We testify if $\Col(A)$ is linearly independent,
by checking if $\ker(A) = \{\bzero\}$.

From row operation, the reduced echlon form of $A$ is:

$$
R=\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1\\
0 & 0 & 0\\
0 & 0 & 0\\
\end{bmatrix}.
$$

Let $\bv=(p, q, r)$.

By solving $R\bv=\bzero$,

$$
\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1\\
0 & 0 & 0\\
0 & 0 & 0\\
\end{bmatrix}\begin{bmatrix}
p\\
q\\
r\\
\end{bmatrix}=\{\bzero\}
$$

we get $\bv=(0, 0, 0)$.

Hence $\bu_1, \bu_2, \bu_3$ are linearly independent.

To write $\bb$ as a linear combination of $S$,
we solve the following equation:

$$
\begin{bmatrix}
1 & -5 & 0\\
-3 & 16 & 3\\
12 & -63 & -8\\
-50 & 264 & 38\\
-28 & 147 & 20\\
\end{bmatrix}\begin{bmatrix}
x\\
y\\
z\\\end{bmatrix}=
\begin{bmatrix}
12\\
-45\\
169\\
-718\\
-397\\
\end{bmatrix}
$$

by writing the above equation as an augumented matrix,

and doing row operation:
$$
\left[\begin{array}{c|c} A & \bb \end{array}\right] = \left[\begin{array}{ccc|c}
1 & -5 & 0 & 12\\
-3 & 16 & 3 & -45\\
12 & -63 & -8 & 169\\
-50 & 264 & 38 & -718\\
-28 & 147 & 20 & -397\\
\end{array}\right]
$$

$$\downarrow
$$

$$
\left[\begin{array}{c|c} R & \br \end{array}\right] =
\left[\begin{array}{ccc|c}
1 & 0 & 0 & -3\\
0 & 1 & 0 & -3\\
0 & 0 & 1 & -2\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
\end{array}\right]
$$

we get $(x, y, z) = (-3, -3, -2)$.

Thus, $\bb = - 3\bu_1 - 3\bu_2 - 2\bu_3$.

##### Exercise 3

以下的例子說明了多項式也有類似地「表示法唯一」的性質。
（有沒有辦法把多項式寫成向量的樣子？）

<!-- eng start -->
The following examples demonstrate that a polynomial can be uniquely represented as a linear combination of some given set of polynomials. This is analogous to the fact that a vector can be uniquely represented as a linear combination of a linearly independent set of vectors. (Can you translate a polynomial into a vectors?)
<!-- 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 if a polynomial $f(x)$ of degree at most $2$ can be written as $c_0 + c_1(x-1) + c_2(x-1)^2$, then the choice of $c_0, c_1, c_2$ is unique.
<!-- eng end -->

:::warning

Mathematics:

No need to change the answer. But the fact that you get $c_i$'s are the same as $k_i$'s is because the matrix

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

is nonsingular. So $A\bc = A{\bf k}$ implies $\bc = {\bf k}$.

Grammar:

- [x] represent of $f(x)$ --> representation of $f(x)$
- [x] Add space after every punctuation.
:::

##### Exercise 3(a) -- answer here

Suppose the representation of $f(x)$ is not unique and it can be represented as $c_0 + c_1(x-1) + c_2(x-1)^2$ and $k_0 + k_1(x-1) + k_2(x-1)^2$.
Expend two functions, we get:
$(c_2-c_1+c_0) + (c_1-2c_2)x + c_2 x^2$.
$(k_2-k_1+k_0) + (k_1-2k_2)x + k_2 x^2$.
And we know that a function's expandable is unique , so
$c_2-c_1+c_0 = k_2-k_1+k_0$， $c_1-2c_2 = k_1-2k_2$, $c_2 = k_2$.
After compute,we get $c_0 = k_0$，$c_1 = k_1$，$c_2 = k_2$.
This contradicts the assumption.
Therefore, the choice of $c_0, c_1, c_2$ is unique.

##### 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 if a polynomial $f(x)$ of degree at most $2$ can be written as $c_1f_1(x) + c_2f_2(x) + c_3f_3(x)$, then the choice of $c_1, c_2, c_3$ is unique.
<!-- eng end -->

---

:::warning

:thumbsup: Math is okay.
:x: However, you need to give explanations to what you are doing. (In fact, the process of the row operations is not the focus --- all we need is the matrix is nonsingular.)

By expanding all polynomials, we get
...
We may record the coefficients of the polynomials as
...
such that the equation

$$
a + bx + cx^2 = c_1f_1(x) + c_2f_2(x) + c_3f_3(x)
$$

is equivalent to

$$
A \begin{bmatrix} c_1 \\ c_2 \\ c_3 \end{bmatrix} =
\begin{bmatrix} a \\ b \\ c \end{bmatrix}.
$$

:::

##### Exercise 3(b) -- answer here

$$
\begin{aligned}
f_1(x) &= \frac{1}{2}x^2-\frac{5}{2}x+3, \\
f_2(x) &= -x^2+4x-3, \\
f_3(x) &= \frac{-1}{2}x^2+\frac{3}{2}x-1. \\
\end{aligned}
$$
\begin{bmatrix}
1/2 & -5/2 & 3\\
-1 & 4 & -3\\
-1/2 & 3/2 & -1
\end{bmatrix}
~\begin{bmatrix}
1 & -5 & 6\\
-1 & 4 & -3\\
-1 & 3 & -2
\end{bmatrix}
~\begin{bmatrix}
1 & -5 & 6\\
0 & -1 & 3\\
0 & -2 & 4
\end{bmatrix}
~\begin{bmatrix}
1 & -5 & 6\\
0 & -1 & 3\\
0 & 0 & -2
\end{bmatrix}
~\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{bmatrix}
$f(x)$=$c_1f_1(x) + c_2f_2(x) + c_3f_3(x)$
the choice of $c_1, c_2, c_3$ is unique

---

##### Exercise 4

證明以下敘述等價：

1. $S$ is linearly independent.
2. For any vector $\bu\in S$, $\bu\notin\vspan(S\setminus\{\bu\})$.
3. For any vector $\bu\in S$, $\vspan(S\setminus\{\bu\})\subsetneq\vspan(S)$.

<!-- eng start -->
Show that the following are equivalent:

1. $S$ is linearly independent.
2. For any vector $\bu\in S$, $\bu\notin\vspan(S\setminus\{\bu\})$.
3. For any vector $\bu\in S$, $\vspan(S\setminus\{\bu\})\subsetneq\vspan(S)$.
<!-- eng end -->

##### Exercise 5

證明以下敘述等價：

1. $S$ is linearly independent.
2. The representation of any linear combination of $S$ is unique.
That is, if $\bb = c_1\bu_1 + \cdots + c_k\bu_k = d_1\bu_1 + \cdots + d_k\bu_k$, then $c_1 = d_1$, $\ldots$, and $c_k = d_k$.
3. For any $\bb\in\Col(A)$, the solution to $A\bx = \bb$ is unique.
4. $\ker(A) = \{\bzero\}$.

<!-- eng start -->
Show that the following are equivalent:

1. $S$ is linearly independent.
2. The representation of any linear combination of $S$ is unique.
That is, if $\bb = c_1\bu_1 + \cdots + c_k\bu_k = d_1\bu_1 + \cdots + d_k\bu_k$, then $c_1 = d_1$, $\ldots$, and $c_k = d_k$.
3. For any $\bb\in\Col(A)$, the solution to $A\bx = \bb$ is unique.
4. $\ker(A) = \{\bzero\}$.
<!-- eng end -->

##### Exercise 6(a)

若 $A$ 是一個 $2\times 2$ 的矩陣且 $\det(A) \neq 0$。
證明 $A$ 的行向量所形成的集合是線性獨立的。

<!-- eng start -->
Suppose $A$ is a $2\times 2$ matrix with $\det(A) \neq 0$. Show that the columns of $A$ form a linearly independent set.
<!-- eng end -->

---

:::warning

Math:

If $u_1$ and $u_2$ are not linear independent, we can assume that $u_2=ku_1$, where $k \neq 0$.
In the sentence above, the condition $k\neq 0$ is not necessary.

Typesetting:

- [x] Use boldface letters for vectors.
:::

##### Exercise 6(a) -- answer here
Soppose a $2\times 2$ matrix $A=\begin{bmatrix}
a_1 & a_2 \\
b_1 & b_2
\end{bmatrix}$, and $\bu_1=(a_1,b_1),\,\bu_2=(a_2,b_2)\in \Col(A)$.

If $\bu_1$ and $\bu_2$ are not linear independent, we can assume that $\bu_2=k\bu_1.$

By calculating $\det(A)$, we get $\det(A)=a_1b_2-a_2b_1=a_1(kb_1)-(ka_1)b_1=0.$

Therefore, if $u_1$ and $u_2$ are not linear independent, we claim that $\det(A)=0$. In other words, if $\det(A) \neq0$, $\bu_1$ and $\bu_2$ are linear independent.

---

##### Exercise 6(b)

若 $A$ 是一個 $3\times 3$ 的矩陣且 $\det(A) \neq 0$。
證明 $A$ 的行向量所形成的集合是線性獨立的。

<!-- eng start -->
Suppose $A$ is a $3\times 3$ matrix with $\det(A) \neq 0$. Show that the columns of $A$ form a linearly independent set.
<!-- eng end -->

:::info
collaboration: 1
4 problems: 3

- done: 2, 3(a), 6(a)
- pending: 3(b)

moderator: 1
quality control: 1
:::