# 判斷矩陣是否可逆

Invertibility

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, 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$.
- $\nul(A) = 0$.
- $\det(A) \neq 0$.

## Side stories

- characteristic polynomial
- Vandermonde matrix
- Sylvester matrix

## Experiments

##### Exercise 1

執行以下程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

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

<!-- eng start -->
Run the code with different `seed` and find an invertible $A$. Then find its inverse $A^{-1}$.
<!-- eng end -->
##### Exercise 1(a) Answer

`set_random_seed(406)`

$$
A = \begin{bmatrix}
1 & -2 & -2 & -2 \\
2 & 0 & 1 & 2 \\
0 & 1 & 2 & 1 \\
0 & 3 & 3 & 1 \\
\end{bmatrix}
$$
(1) By using Laplace’s expansion, we get $\det(A)=12\neq 0.$
So $A$ is invertible.
(2) The reduced echelon form of $\left[\begin{array}{c|c} A & I \end{array}\right]$ is $\left[\begin{array}{c|c} I & A^{-1} \end{array}\right]$.
Then, we get
$$
A^{-1} = \begin{bmatrix}
\frac{1}{3} & \frac{1}{3} & -\frac{1}{3} & \frac{1}{3} \\
-\frac{1}{6} & \frac{1}{12} & -\frac{13}{12} & \frac{7}{12} \\
\frac{1}{3} & -\frac{1}{6} & \frac{7}{6} & -\frac{1}{6} \\
-\frac{1}{2} & \frac{1}{4} & -\frac{1}{4} & -\frac{1}{4} \\
\end{bmatrix}.
$$

##### Exercise 1(b)

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

<!-- eng start -->
Run the code with different `seed` and find singular $A$. Then find a nonzero vector in $\ker(A)$.
<!-- eng end -->

##### Exercise 1(b) Answer

`set_random_seed(100)`

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

(1) By using Laplace’s expansion, we get $\det(A)=0.$
So $A$ is singular.
(2) $\ker(A)=\Col
\begin{bmatrix}
0\\1\\0\\-1
\end{bmatrix} \neq \{\bzero\}$

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

Answer:

When a matrix $A$ is invertible, its determinant is not equal to $0$.

On the other hand, when $A$ is not, its determinant is equal to $0$ and $\ker(A)$ is not equal to $\{\bzero\}$.

:::

## Exercises

##### Exercise 2

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

<!-- eng start -->
For each of following matrices, find all possible $x$ such that $A$ is singular.
<!-- eng end -->

##### Exercise 2(a)

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

**Ans:**
To find all possible $x$ that make $A$ singular, we have to let $\det(A)=0$.
By applying the elements in the above matrix to the formula for finding a 2x2 matrice's determinant,
we get:
$$
\det(A)=(1-x)\cdot(4-x)-2\cdot3=x^2-5x-2=0
$$
$$
x=\frac{5}{2}+\frac{\sqrt{29}}{2}
$$
or
$$\frac{5}{2}-\frac{\sqrt{29}}{2}
$$

:::warning
Make the sentences complete.
:::

##### Exercise 2(b)

$$
A = \begin{bmatrix}
2 - x & 3 \\
3 & 2 - x
\end{bmatrix}.
$$
A singular matrix means its determinant value has to be $0$ so that
$A^{-1}$ does not exists (not invertible).
Therefore, we have to let $\det(A)=(2-x)(2-x)-9=0$.
By calculation, $x=5$ or $x=-1$.

##### Exercise 2\(c\)

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

**Ans:**
$A$ is singular, so $\det(A)=0$.
$\det(A)=-x^3+3x^2=0$
$x=0$ or $3$

:::warning
Make the sentences complete.
:::

##### Exercise 2(d)

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

##### Exercise 2(d) Answer (Ken)
Because $A$ is singular, $\det(A)=0$.
By using Laplace’s expansion, we get $\det(A)=(1-x)[(1-x)^2-2]=0.$
Then we get the equation $-x^3+3x^2-x-1=0$.
After solving, we get $x=1$ or $x=1\pm \sqrt2$.

##### 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$。

<!-- eng start -->
Given distinct real numbers $\lambda_0, \ldots, \lambda_d$, the associated Vandermonde matrix is

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

(See 311 for more details.)

We knew that

$$
\det(A) = \prod_{j > i} (\lambda_j - \lambda_i).
$$

Therefore, the determinant of $A$ is nonzero whenever $\lambda_0, \ldots, \lambda_d$ are distinct.

Use this property to show:
Given any $d + 1$ distinct real numbers $\lambda_0, \ldots, \lambda_d$ and any $d+1$ real numbers $y_0, \ldots, y_d$, there must be a unique polynomial $p$ of degree at most $d$ such that $p(\lambda_0) = y_0, \ldots, p(\lambda_d) = y_d$.
<!-- eng end -->

##### Exercise 4

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

<!-- eng start -->
See 312 for the definition and the properties of a Sylvester matrix.
<!-- eng end -->

##### Exercise 4(a)

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

<!-- eng start -->
Let $p = 2 - 3x + x^2$ and $q = 6 + 11x + 6x^2 + x^3$. Determine if $\gcd(p,q) = 1$ or not.
<!-- eng end -->

**[由 :cloud: 提供]**
### Exercise 4(a) -- answer
Sylvester matrix :

$$
S_{p,q} = \begin{bmatrix}
| & ~ & | & | & ~ & | \\
[p]_\beta & \cdots & [x^{n-1}p]_\beta & [q]_\beta & \cdots & [x^{m-1}q]_\beta \\
| & ~ & | & | & ~ & | \\
\end{bmatrix}.
$$

We plug in $n=2$ , $m=3$ , $p= 2 - 3x + x^2$ , $q= 6 + 11x + 6x^2 + x^3$ to get the Sylvester matrix of $p,q$ :

$$
A=\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}
$$
After calculating the determinant. $\det(A)\neq 0$, which means $A$ is invertable and $\gcd(p,q) = 1$.

##### Exercise 4(b)

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

<!-- eng start -->
Let $p = 2 - 3x + x^2$ and $q = -6 + x + 4x^2 + x^3$. Determine if $\gcd(p,q) = 1$ or not.
<!-- eng end -->

**[由 :cloud: 提供]**
### Exercise 4(b) -- answer

We plug in $n=2$ , $m=3$ , $p= 2 - 3x + x^2$ , $q= -6 + x + 4x^2 + x^3$ to get the Sylvester matrix of $p,q$ :

$$
A=\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}
$$

After calculating the determinant. $\det(A)= 0$, which means $A$ is singular and $\gcd(p,q) \neq 1$.

##### Exercise 4(c)

已知以下兩敘述等價。

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

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

<!-- eng start -->
Suppose we know the following are equivalent.

- The polynomial $p$ has a multiple root.
- $p$ and $p'$ have a common root.

Use this fact to determine whetehr $p = 3 - 5x + x^2 + x^3$ has a multiple root.
<!-- eng end -->

**[由 :cloud: 提供]**
### Exercise 4(c) -- answer

Since $p=3-5x+x^2+x^3$, we have $p'=-5+2x+3x^2$. We need to check whether $p$ and $p'$ have a common root.

Suppose $r$ is a common root of $p$ and $p'$. Then, we have $p(r) = 0$ and $p'(r) = 0$.
Using the expressions for $p$ and $p'$, we get the following equations:

$$
\begin{aligned} 3-5r+r^2+r^3 &= 0 \\ -5+2r+3r^2 &= 0 \end{aligned}
$$

Solving the second equation for $r$, we get $r = 1$ and $r=\displaystyle \frac{10}{6}$. We can substitute these values of $r$ into the first equation to check if they satisfy it.
After some algebraic manipulation, we find that neither of the values of $r$ satisfy the first equation. Therefore, $p$ and $p'$ do not have a common root, and hence $p$ does not have a multiple root.

:::info
Alternatively, you may check if $\gcd(p,p') = 1$ or not by the Sylvester matrix. Thus, you do not need to solve the equation.
:::

##### Exercise 4(d)

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

<!-- eng start -->
Let $p = c + bx + ax^2$ be a polynomial of degree $2$ with $a\neq 0$. Find a criterion on $a,b,c$ for $p$ having a multiple root.
<!-- eng end -->

##### Exercise 4(e)

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

<!-- eng start -->
Let $p = d + cx + bx^2 + ax^3$ be a polynomial of degree $2$ with $a\neq 0$. Find a criterion on $a,b,c,d$ for $p$ having a multiple root.
<!-- eng end -->

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

<!-- eng start -->
Suppose we know $\ker(A) = \ker(A\trans A)$. (See 105-2.)

Let

$$
A = \begin{bmatrix}
1 & 1 & 1 \\
-1 & 1 & 1 \\
1 & -1 & 1 \\
1 & 1 & -1
\end{bmatrix}.
$$
<!-- eng end -->

##### Exercise 5(a)

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

<!-- eng start -->
Find $\det(A\trans A)$.
<!-- eng end -->

##### Exercise 5(a) answer by Kevin
$$
A\trans = \begin{bmatrix}
1 & -1 & 1 & 1\\
1 & 1 & -1 & 1\\
1 & 1 & 1 & -1
\end{bmatrix}.
$$
By calculation,
$$
A\trans A = \begin{bmatrix}
4 & 0 & 0\\
0 & 4 & 0\\
0 & 0 & 4
\end{bmatrix}.
$$
Thus, by the properties of determinants,

$$
\det(A\trans A)=64.
$$

##### Exercise 5(b)

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

<!-- eng start -->
Use $\det(A\trans A)$ to determine if the columns of $A$ form an independent set.
<!-- eng end -->

:::info

collaboration: 1
4 problems: 4

* 2a~d

extra: 0.5

* 5a

moderator: 1
qc: 1
:::