# 判斷矩陣是否可逆

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}}$

from lingeo import random_int_list, kernel_matrix

## Main idea

In this section, we emphasize the relation between the determinant and the invertibility of a matrix.
For any $n\times n$ matrix $A$, the matrix $A$ is invertible if and only if $\det(A) \neq 0$.

Here we summarize some equivalent conditions.
Let $A$ be an $n\times n$ matrix.
Then the following are equivalent.

- $A$ is invertible.
- $\Col(A) = \mathbb{R}^n$.
- $\ker(A) = \{\bzero\}$.
- $\rank(A) = n$.
- $\det(A) \neq 0$.

## Side stories

- characteristic polynomial
- Vandermonde matrix
- Sylvester matrix

## Experiments

##### Exercise 1

執行以下程式碼。

### code
set_random_seed(0)
print_ans = False

inv = choice([True, False])

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

print("A =")
pretty_print(A)

if print_ans:
    print("Invertible?", inv)
    if inv:
        print("A inverse =")
        pretty_print(A.inverse())
    else:
        print("The kernel of A is the column space of")
        pretty_print(kernel_matrix(A))

##### Exercise 1(a)

嘗試不同的 `seed` ，
找出一個可逆矩陣 $A$、
並求出 $A^{-1}$。

:::warning

- [x] _seed_ = 5 --> `seed = 5`
- [x] $det$ --> $\det$
- [x] 他的反矩陣應該是叫 $A^{-1}$ 不叫 $A$
:::

**答:**
當 `seed = 5` 時，經過列運算可以得知 **$\det(A) \not= 0$** 。
所以可以找出一可逆矩陣，
$$
A = \begin{bmatrix}
1 & -2 & -1 & -1\\
-2 & 1 & -2 & -1\\
-2 & 0 & 3 & -1\\
1 & -1 & -3 & 3\\
\end{bmatrix}.
$$
且他的反矩陣為，
$$
A^{-1} = \begin{bmatrix}
\frac{-1}{67} & \frac{-16}{67} & \frac{-25}{67} & \frac{-14}{67}\\
\frac{-25}{67} & \frac{2}{67} & \frac{-22}{67} & \frac{-15}{67}\\
\frac{-5}{67} & \frac{-13}{67} & \frac{9}{67} & \frac{-3}{67}\\
\frac{-13}{67} & \frac{-7}{67} & \frac{10}{67} & \frac{19}{67}\\
\end{bmatrix}.
$$

##### Exercise 1(b)

嘗試不同的 `seed` ，
找出一個不可逆矩陣 $A$、
並求出一個 $\ker(A)$ 中的非零項量。

:::warning

- [x] 依上一題建議修改
- [x] $\ker(A)$ 是集合，但等號右邊是向量
:::

**答:**

當 `seed = 1` 時，經過列運算可以得知 **$\det(A) = 0$** 。
所以可以找出一不可逆矩陣，
$$
A = \begin{bmatrix}
-1 & 3 & 3 & 1\\
-1 & 3 & 2 & 3\\
0 & 0 & -2 & 3\\
1 & -3 & 2 & -3\\
\end{bmatrix}.
$$
且可求出 $\ker(A)$ 中的一個非零向量 $(3,1,0,0)$ 。

## Exercises

##### Exercise 2

對以下矩陣，求出所有讓 $A$ 不可逆的 $x$。

:::warning

- [x] $det$ --> $\det$
- [x] 標點
:::

**註:當 $A$ 可逆時， $A$ 在經過高斯消去法後可以形成 $I_n$ 的倍數，即 $\det(A) \neq 0$。**

**而此題要使 $A$ 不可逆，也就是讓** $\det(A)=0$

##### Exercise 2(a)

$$
A = \begin{bmatrix}
1 - x & 2 \\
3 & 4 - x
\end{bmatrix}.
$$

**答:**

$\det(A)=(1-x)\cdot(4-x)-2\cdot3
=x^2-5x-2$，

再運用配方法，得 $x^2-5x-2=(x-\frac{5}{2})^2-\frac{29}{4}=0$。

求得當 $x=\frac{5}{2}+\frac{\sqrt{29}}{2}$ 或 $\frac{5}{2}-\frac{\sqrt{29}}{2}$ 時， $A$ 不可逆。

##### Exercise 2(b)

$$
A = \begin{bmatrix}
2 - x & 3 \\
3 & 2 - x
\end{bmatrix}.
$$

:::warning

- [x] 同上題
:::

**答:**

$\det(A)=(2-x)\cdot(2-x)-3\cdot3=x^2-4x-5$，

藉由因式分解法，得$x^2-4x-5=(x-5)\cdot(x+1)$，

即當 $x=-1$ 或 $5$ 時， $A$ 不可逆。

##### Exercise 2(c)

$$
A = \begin{bmatrix}
1 - x & 1 & 1 \\
1 & 1 - x & 1 \\
1 & 1 & 1 - x
\end{bmatrix}.
$$

:::warning

- [x] $A$ 不會一下是這個矩陣、一下是那個矩陣，建議可以用 $A_1$、$A_2$、$A_3$ 等等。
- [x] 乘到 --> 加到？
- [x] 讓 $A$ 矩陣無法形成 $I_n$ 的倍數 --> 讓 $A$ 矩陣的對角線出現 $0$

PS 你算的那個其實就是行列式值
:::

**答:**

對 $A$ 使用高斯消去法，交換 $A$ 的第一列和第三列，得

$$
A_1 =-\begin{bmatrix}
1 & 1 & 1-x \\
1 & 1-x & 1 \\
1-x & 1 & 1
\end{bmatrix}.
$$

再將新的第一列以 $-1$倍 加到第二列以及第三列，得

$$
A_2 =-\begin{bmatrix}
1 & 1 & 1-x \\
0 & -x & x \\
0 & x & -x^2+2x+2
\end{bmatrix}.
$$

最後將第二列以 $-1$倍 加到第三列，得
$$
A_3 =-\begin{bmatrix}
1 & 1 & 1-x \\
0 & -x & x \\
0 & 0 & -x^2+3x
\end{bmatrix}.
$$
要使 $A_3$ 不可逆的話，等價於使其 $\det(A) = 0$ ，即要使 $A_3$ 矩陣的對角線出現 $0$。

使 $x=0$ 或 $-x^2+3x=0$，即當 $x=0$ 或 $3$ 的時候， $A$ 矩陣不可逆。

##### Exercise 2(d)

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

:::warning

- [x] 參考上一題的問題
- [x] 標點有少
:::

**答:**

對 $A$ 使用高斯消去法，交換 $A$ 的第二列和第三列，得

$$
A_1 =-\begin{bmatrix}
1 & 1-x & 1 \\
1-x & 1 & 0 \\
0 & 1 & 1-x
\end{bmatrix}.
$$

再將新的第一列以 $x-1$倍 加到第二列以及第三列，得

$$
A_2 =-\begin{bmatrix}
1 & 1-x & 1 \\
0 & -x^2+2x & x-1 \\
0 & 1 & 1-x
\end{bmatrix}.
$$

接著交換 $A$ 的第二列和第三列，得

$$
A_3 =-\begin{bmatrix}
1 & 1-x & 1 \\
0 & 1 & 1-x \\
0 & -x^2+2x & x-1
\end{bmatrix}.
$$

最後將第二列以 $x^2-2x$ 倍 加到第三列，得
$$
A_4 =-\begin{bmatrix}
1 & 1-x & 1 \\
0 & 1 & 1-x \\
0 & 0 & -x^3+3x_2-x-1
\end{bmatrix}.
$$
要使 $A_4$ 不可逆的話，等價於使其 $\det(A) = 0$ ，即要使 $A_4$ 矩陣的對角線出現 $0$。

藉由勘根定理，我們可以發現 $x=1$ 是 $-x^3 + 3x_2 - x-1$ 的根。

接著我們將 $-x^3+3x_2-x-1$ 除以 $x-1$，得到商為 $-x^2+2x+1$ .

再將 $-x^2+2x+1$ 配方後得到 $-(x-1)^2+2=0$ ,

即當 $x=1$、$1+\sqrt{2}$ 或 $1-\sqrt{2}$ 時， $A$ 矩陣不可逆。

##### Exercise 3

給定相異實數 $\lambda_0, \ldots, \lambda_d$，
其所對應的凡德孟矩陣為
$$
A = \begin{bmatrix}
1 & \lambda_0 & \cdots & \lambda_0^d \\
1 & \lambda_1 & \cdots & \lambda_1^d \\
\vdots & \vdots & ~ & \vdots \\
1 & \lambda_d & \cdots & \lambda_d^d
\end{bmatrix}.
$$
（相關性質請見 311。）
已知
$$
\det(A) = \prod_{j > i} (\lambda_j - \lambda_i).
$$
所以當 $\lambda_0, \ldots, \lambda_d$ 相異時其凡德孟矩陣的行列式值一定非零。

利用這個性質證明：
給定 $d+1$ 個相異實數 $\lambda_0, \ldots, \lambda_d$、
並給定 $d+1$ 個實數 $y_0, \ldots, y_d$，
則必存在唯一一個 $d$ 次以下的多項式 $p$ 使得 $p(\lambda_0) = y_0, \ldots, p(\lambda_d) = y_d$。

**[由黃佑祥同學提供]**
**回顧凡德孟矩陣性質:**
1. 必定可逆
2. 必定存在反矩陣

設一多項式 $p = c_0 + c_1 \cdot x + \cdots + c_d \cdot x^d$，
其中 $c_0, \cdots ,c_d$ 為多項式 $p$ 的係數。

依題意 $p(\lambda_0) = y_0, \ldots, p(\lambda_d) = y_d$ ，我們可以寫出一恆等式

$$
\begin{bmatrix}
1 & \lambda_0 & \cdots & \lambda_0^d \\
1 & \lambda_1 & \cdots & \lambda_1^d \\
\vdots & \vdots & ~ & \vdots \\
1 & \lambda_d & \cdots & \lambda_d^d
\end{bmatrix}
\cdot
\begin{bmatrix}
c_0\\
c_1 \\
\vdots \\
c_d
\end{bmatrix}=
\begin{bmatrix}
y_0 \\
y_1 \\
\vdots \\
y_d\end{bmatrix}.
$$

由於 $A$ 是凡德孟矩陣，所以必定可逆，得

$$
\begin{bmatrix}
c_0\\
c_1 \\
\vdots \\
c_d
\end{bmatrix}=
A^{-1}
\cdot
\begin{bmatrix}
y_0 \\
y_1 \\
\vdots \\
y_d\end{bmatrix}.
$$

因為 $A$ 中的 $\lambda_0 \cdots \lambda_d$ 是相異的，
而題目又提及當 $\lambda_0, \ldots, \lambda_d$ 相異時，
其凡德孟矩陣的行列式值一定非零。

即對於任意 $i \gt j$ ，我們可以得到 $\lambda_i - \lambda_j \neq 0$ 。

所以 $\begin{bmatrix}
c_0\\
c_1\\
\vdots\\
c_d
\end{bmatrix}$ 可以被唯一決定。

##### Exercise 4

參考 312 中西爾維斯特矩陣的定義及性質。

##### Exercise 4(a)

給定兩多項式
$p = 2 - 3x + x^2$、
$q = 6 + 11x + 6x^2 + x^3$。
判斷 $p$ 和 $q$ 是否互質。

:::success
Nice!
:::

**答:**

利用西爾維斯特矩陣，得

$$
\begin{bmatrix}
2 & 0 & 0 & 6 & 0 \\
-3 & 2 & 0 & 11 & 6 \\
1 & -3 & 2 & 6 & 11 \\
0 & 1 & -3 & 1 & 6 \\
0 & 0 & 1 & 0 & 1
\end{bmatrix}.
$$

經由高斯消去法，最後得其行列式值為 $1440$ 。
因行列式值不為 $0$ ，故此矩陣可逆，相當於此兩多項式互質。

##### Exercise 4(b)

給定兩多項式
$p = 2 - 3x + x^2$、
$q = -6 + x + 4x^2 + x^3$。
判斷 $p$ 和 $q$ 是否互質。

**答:**

利用西爾維斯特矩陣，得
$$
\begin{bmatrix}
2 & 0 & 0 & -6 & 0 \\
-3 & 2 & 0 & 1 & -6 \\
1 & -3 & 2 & 4 & 1 \\
0 & 1 & -3 & 1 & 4 \\
0 & 0 & 1 & 0 & 1
\end{bmatrix}
$$

經由高斯消去法，最後得其行列式值為 $0$ 。
因行列式值為 $0$ ，故此矩陣不可逆，相當於此兩多項式不互質。

##### Exercise 4(c)

已知以下兩敘述等價。

- 多項式 $p$ 有重根。
- $p$ 和 $p'$ 有共同根。

利用這個性質判斷 $p = 3 - 5x + x^2 + x^3$ 是否有重根。

**答:**

由題得 $p' = -5 + 2x + 3x^2$ 。
利用西爾維斯特矩陣，得
$$
\begin{bmatrix}
3 & 0 & -5 & 0 & 0 \\
-5 & 3 & 2 & -5 & 0 \\
1 & -5 & 3 & 2 & -5 \\
1 & 1 & 0 & 3 & 2 \\
0 & 1 & 0 & 0 & 3
\end{bmatrix}
$$

經由高斯消去法，最後得其行列式值為 $0$ 。
因行列式值為 $0$ ，故此矩陣不可逆，相當於此兩多項式有共同根。
依上述性質，此多項式 $p$ 有重根。

##### Exercise 4(d)

令 $p = c + bx + ax^2$ 為一二次多項式（$a\neq 0$）。
求 $a,b,c$ 在什麼條件下會有重根。

**答:**

因 $p = c + bx + ax^2$ ，故 $p' =b + 2ax$。
利用西爾維斯特矩陣，得
$$
\begin{bmatrix}
c & b & 0\\
b & 2a & b\\
a & 0 & 2a
\end{bmatrix}
$$
而此矩陣行列式值相等於 $-a(b^2-4ac)$ 。
故當 $$ b^2-4ac = 0 $$ 時，此矩陣不可逆，而依 4(c) 的性質，此時 $p$ 有重根。

##### Exercise 4(e)

令 $p = d + cx + bx^2 + ax^3$ 為一三次多項式（$a\neq 0$）。
求 $a,b,c,d$ 在什麼條件下會有重根。

**[由黃佑祥同學提供]**
利用 4(c) 的性質，也就是方程式有重根，等價於 $p$ 和 $p'$ 有共同根。

先求出 $p = ax^3 + bx^2 + cx +d$，
以及 $p'= 3ax^2 + 2bx + c$。

接著利用西爾維斯特矩陣，得
$$
A=\begin{bmatrix}
a & 0 & 3a & 0 & 0 \\
b & a & 2b & 3a & 0 \\
c & b & c & 2b & 3a \\
d & c & 0 & c & 2b \\
0 & d & 0 & 0 & c
\end{bmatrix}.
$$

得到
$$\det(A) =
-a b^{2} c^{2} + 4 \, a^{2} c^{3} + 4 \, a b^{3} d - 18 \, a^{2} b c d + 27 \, a^{3} d^{2},
$$

而當 $\det(A) = 0$ 的時候，此矩陣不可逆。

而 $A$ 矩陣不可逆等價於 $p$ 和 $p'$ 有共同根，也就等價於方程式有重根。

##### Exercise 5

已知對任意矩陣 $\ker(A) = \ker(A\trans A)$。
（參考 105-2。）

令
$$
A = \begin{bmatrix}
1 & 1 & 1 \\
-1 & 1 & 1 \\
1 & -1 & 1 \\
1 & 1 & -1
\end{bmatrix}.
$$

##### Exercise 5(a)

求 $\det(A\trans A)$。

**答:**
$$
A\trans A = \begin{bmatrix}
4 & 0 & 0 \\
0 & 4 & 0 \\
0 & 0 & 4
\end{bmatrix}，
$$
$\det(A\trans A) = 64。$

##### Exercise 5(b)

利用 $\det(A\trans A)$ 判斷 $A$ 的行向量集是否線性獨立。
:::warning

- [x] 中英數間空格
- [x] 最後一句的因果關係沒講清楚
:::

**答:** $A\trans A$ 可逆，則 $\ker(A\trans A) = \{\bzero\}$。由條件 $\ker(A\trans A) = \ker(A)$ 可知 $\ker(A) = \{\bzero\}$。即方程式 $A\bx = \bzero$ 的只有 $\bzero$， 故 $A$ 的行向量集獨立。

:::info
目前分數 = 5 ± 檢討 = 6.5
:::