判斷矩陣是否可逆

Invertibility

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

執行以下程式碼。

Run the code below.

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

Run the code with different seed and find an invertible $A$. Then find its inverse $A^{-1}$.

Exercise 1(b)

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

Run the code with different seed and find an invertible $A$. Then find a nonzero vector in $\ker(A)$.

Exercises

Exercise 2

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

For each of following matrices, find all possible $x$ such that $A$ is singular.

Exercise 2(a)

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

Exercise 2(b)

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

Exercise 2(c)

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

Exercise 2(d)

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

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

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

Exercise 4

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

See 312 for the definition and the properties of a Sylvester matrix.

Exercise 4(a)

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

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

Exercise 4(b)

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

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

Exercise 4(c)

已知以下兩敘述等價。

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

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

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.

Exercise 4(d)

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

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.

Exercise 4(e)

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

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.

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

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

Exercise 5(a)

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

Find $\det(A\trans A)$.

Exercise 5(b)

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

Use $\det(A\trans A)$ to determine if the columns of $A$ form an independent set.