This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
Coefficients of the characteristic polynomial
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, random_good_matrix
Let $A$ be an $n\times n$ matrix.
Let $\alpha \subseteq [n]$ be a subset of indices.
We let $A[\alpha]$ be the submatrix of $A$ induced on rows and columns in $\alpha$.
Such a matrix is called a principal submatrix of $A$, and its determinant is called a principal minor.
Let $s_k = s_k(A)$ be the sum of all $k\times k$ principal minors.
Vacuously, we define $s_0 = 1$.
Then
In particular,
$s_1 = \tr(A)$ is the sum of all diagonal entries of $A$, and
$s_n = \det(A)$.
This identity follows from the expansion of the characteristic polynomial by the distributive law on each column.
Here is an example.
### code
set_random_seed(0)
print_ans = False
n = 3
spec = random_int_list(n, 3)
D = diagonal_matrix(spec)
Q = random_good_matrix(n,n,n,2)
A = Q * D * Q.inverse()
pretty_print(LatexExpr("A ="), A)
if print_ans:
for k in [3,2,1]:
print("k =", k)
kmtx = []
kmnr = []
for alpha in Combinations(list(range(3)), k):
kmtx.append(A[alpha, alpha])
kmnr.append(A[alpha, alpha].det())
print("all k x k principal submatricies:")
pretty_print(*kmtx)
print("all k x k principal minors:")
print(kmnr)
print("sk =", sum(kmnr))
print("---")
pA = (-1)^n * A.charpoly()
print("characteristic polyomial =", pA)
print("spectrum is the set { " + ", ".join("%s"%val for val in spec) + " }")
列出所有的 $3\times 3$ 主子矩陣，並計算 $s_3$。
List all the $3\times 3$ principal submatrices and find $s_3$.
列出所有的 $2\times 2$ 主子矩陣，並計算 $s_2$。
List all the $2\times 2$ principal submatrices and find $s_2$.
列出所有的 $1\times 1$ 主子矩陣，並計算 $s_1$。
List all the $1\times 1$ principal submatrices and find $s_1$.
利用 $s_k$ 計算以下矩陣 $A$ 的特徵多項式以及 $\spec(A)$。
Find the characteristic polynomial of $A$ and $\spec(A)$ through $s_k$.
利用 $s_k$ 計算以下矩陣 $A$ 的特徵多項式以及 $\spec(A)$。
Find the characteristic polynomial of $A$ and $\spec(A)$ through $s_k$.
令 $J_n$ 為 $n\times n$ 的全 $1$ 矩陣。
對每一個 $k = 0,\ldots, n$，計算 $s_k$，
並藉此求 $J_n$ 的特徵多項式及 $\spec(J_n)$。
Let $J_n$ be the $n\times n$ all-ones matrix. For each of $k = 0,\ldots, n$, find $s_k$. Then use them to find the characteristic polynomial of $J_n$ and $\spec(J_n)$.
令 $J_{m,n}$ 為 $m\times n$ 的全 $1$ 矩陣，而
$$ A = \begin{bmatrix} O_{n,n} & J_{n,m} \\ J_{m,n} & O_{m,m} \end{bmatrix}. $$對每一個 $k = 0,\ldots, n$，計算 $s_k$，
並藉此求 $A$ 的特徵多項式及 $\spec(A)$。
Let $J_{m,n}$ be the $m\times n$ all-ones matrix and
$$ A = \begin{bmatrix} O_{n,n} & J_{n,m} \\ J_{m,n} & O_{m,m} \end{bmatrix}. $$For each of $k = 0,\ldots, n$, find $s_k$. Then use them to find the characteristic polynomial of $J_n$ and $\spec(J_n)$.
令 $A$ 為一 $n\times n$ 矩陣。
若特徵多項式 $p_A(x) = s_0(-x)^n + s_1(-x)^{n-1} + \cdots + s_n$ 的根為 $\lambda_1,\ldots,\lambda_n$，則
如此一來我們就有根與係數的關係
$$ \begin{aligned} s_0 &= 1, \\ s_1 &= \lambda_1 + \cdots + \lambda_n, \\ s_2 &= \sum_{i<j}\lambda_i\lambda_j, \\ \vdots & \\ s_n &= \lambda_1\cdots\lambda_n. \end{aligned} $$Let $A$ be an $n\times n$ matrix. Let $\lambda_1,\ldots,\lambda_n$ be the roots of the characteristic polynomial $p(A) = s_0(-x)^n + s_1(-x)^{n-1} + \cdots + s_n$. Then
$$ p_A(x) = (\lambda_1 - x) \cdots (\lambda_n - x). $$Thus, Vieta's formulas describe the relations between the coefficients of a polynomial and its roots by
$$ \begin{aligned} s_0 &= 1, \\ s_1 &= \lambda_1 + \cdots + \lambda_n, \\ s_2 &= \sum_{i<j}\lambda_i\lambda_j, \\ \vdots & \\ s_n &= \lambda_1\cdots\lambda_n. \end{aligned} $$令 $J_n$ 為 $n\times n$ 的全 $1$ 矩陣。
若已知 $\spec(J_n)$ 中有 $n-1$ 個零，
求最後一個特徵值。
（未來會發現這雖然是求 $\spec(J_n)$，
但也可以反推特徵多項式，
所以請不要用先前題目的結果來計算這題。）
Let $J_n$ be the $n\times n$ all-ones matrix. It is known that $\spec(J_n)$ contains $n-1$ copies of $0$. Find the last eigenvalues.
(In the future we will see that $\spec(J_n)$ can be used to find the characteristic polynomial, so please do not use the previous results on the characteristic polynomial to solve this problem.)
令 $J_{m,n}$ 為 $m\times n$ 的全 $1$ 矩陣，而
$$ A = \begin{bmatrix} O_{n,n} & J_{n,m} \\ J_{m,n} & O_{m,m} \end{bmatrix}. $$若已知 $\spec(A)$ 中有 $n-2$ 個零，
求最後兩個特徵值。
（未來會發現這雖然是求 $\spec(A)$，
但也可以反推特徵多項式，
所以請不要用先前提目的結果來計算這題。）
Let $J_{m,n}$ be the $m\times n$ all-ones matrix and
$$ A = \begin{bmatrix} O_{n,n} & J_{n,m} \\ J_{m,n} & O_{m,m} \end{bmatrix}. $$It is known that $\spec(J_n)$ contains $n-2$ copies of $0$. Find the last two eigenvalues.
(In the future we will see that $\spec(J_n)$ can be used to find the characteristic polynomial, so please do not use the previous results on the characteristic polynomial to solve this problem.)
證明若 $A$ 和 $B$ 相似
（也就是存在可逆的 $Q$ 使得 $B = Q^{-1}AQ$），
則對每一個 $k = 0,\ldots, n$ 都有 $s_k(B) = s_k(A)$。
因此我們也可以把任一線性函數 $f:V\rightarrow V$ 的 $s_k(f)$ 定義成 $s_k([f]_\beta^\beta)$，
其中 $\beta$ 可以是 $V$ 的任意基底。
Show that if $A$ and $B$ are similar (meaning $B = Q^{-1}AQ$ for some invertible matrix $Q$), then $s_k(B) = s_k(A)$ for each $k = 0,\ldots, n$.
Therefore, for any linear function $f:V\rightarrow V$, we may define $s_k(f)$ as $s_k([f]_\beta^\beta)$, where $\beta$ could be any basis.
令 $A$ 與 $B$ 分別為 $m\times n$ 與 $n\times n$ 矩陣，且 $m\leq n$。
若 $\alpha\subseteq [n]$ 是一些下標的集合，
定義 $A[:,\alpha]$ 是由 $A$ 中 $\alpha$ 裡的那些行所組成的 $m\times |\alpha|$ 矩陣，
而 $B[\alpha,:]$ 是由 $B$ 中 $\alpha$ 裡的那些列所組成的 $|\alpha|\times m$ 矩陣。
Let $A$ and $B$ be $m\times n$ and $n\times n$ matrices with $m\leq n$. Let $\alpha\subseteq [n]$ be an index set. Define $A[:,\alpha]$ as the $m\times |\alpha|$ matrix obtained from $A$ by collecting those columns in $\alpha$. Similarly, define $B[\alpha,:]$ as the $|\alpha|\times m$ matrix obtained from $A$ by collecting those rows in $\alpha$.
令
$$ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \text{ and } B = \begin{bmatrix} 7 & 8 \\ 9 & 10 \\ 11 & 12 \end{bmatrix}. $$對所有大小為 $2$ 的集合 $\alpha\subseteq [3]$，
求出所有的 $A[:,\alpha]$ 及 $B[\alpha,:]$，
並利用柯西比內公式計算 $AB$ 的行列式值。
Let
$$ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \text{ and } B = \begin{bmatrix} 7 & 8 \\ 9 & 10 \\ 11 & 12 \end{bmatrix}. $$For each $\alpha\subseteq [3]$ of size $2$, find $A[:,\alpha]$ and $B[\alpha,:]$. Then use the Cauchy–Binet formula to find the determinant of $AB$.
令
$$ M = \begin{bmatrix} O_{n,n} & B \\ A & O_{m,m} \end{bmatrix}. $$利用 506-6 求出 $p_M(x)$ 的 $(-x)^{n-m}$ 項係數。
Let
$$ M = \begin{bmatrix} O_{n,n} & B \\ A & O_{m,m} \end{bmatrix}. $$Use the results in 506-6 to find the coefficient of $(-x)^{n-m}$ in $p_M(x)$.
令
$$ M = \begin{bmatrix} O_{n,n} & B \\ A & O_{m,m} \end{bmatrix}. $$利用 $s_{2m}$ 的定義直接求出 $s_{2m}(M)$。
配合上一題證明柯西比內公式。
Let
$$ M = \begin{bmatrix} O_{n,n} & B \\ A & O_{m,m} \end{bmatrix}. $$Find $s_{2m}(M)$ by definition. Then use the previous problem to show the Cauchy–Binet formula.
令 $A$ 為一 $n\times n$ 矩陣。
將 $p_A(x)$ 代入 $x = 0$ 可得
類似地，我們可以利用 506-10 計算
$$ s_{n-1} = -\frac{dp_A(x)}{dx}\Big|_{x=0} = \sum_{i = 1}^n p_{A(i)}(x)\Big|_{x=0} = \sum_{i=1}^n\det(A(i)). $$利用數學歸納法證明
$$ \det(A - xI) = s_0(-x)^n + s_1(-x)^{n-1} + \cdots + s_n. $$Let $A$ be an $n\times n$ matrix. By substituting $x = 0$ in $p_A(x)$, we have
$$ s_n = p_A(0) = \det(A - 0I) = \det(A). $$Similarly, we may use the results in 506-10 to find
$$ s_{n-1} = -\frac{dp_A(x)}{dx}\Big|_{x=0} = \sum_{i = 1}^n p_{A(i)}(x)\Big|_{x=0} = \sum_{i=1}^n\det(A(i)). $$Prove that
$$ \det(A - xI) = s_0(-x)^n + S_1(-x)^{n-1} + \cdots + s_n $$by induction.