Chapter 4. Eigenvalues and Eigenforms
Recommended article: 【Linear Algebra】 Linear Algebra Contents
1. Eigenvalues and Eigenvectors
2. Diagonalization of Matrices
1. Eigenvalues and Eigenvectors
⑴ Eigenvalues and eigenvectors
① Overview: Used in diagonalizability, spectral clustering, etc.
② Theorem 1. The necessary and sufficient condition for A - λI to have a non-zero kernel in (A - λI)x = 0 is det(A - λI) = 0.
○ Proof: rank-nullity theorem
③ Theorem 2. When the eigenvalues of A ∈ ℝ2×2 are λ1, λ2, A2 - (λ1 + λ2)A + λ1λ2I = O holds.
○ Proof
From the definition of eigenvalues, the following holds.
From this, it is easily known that λ1 + λ2 = a + d, and λ1λ2 = ad - bc.
Therefore, by the Cayley-Hamilton theorem, the above proposition holds.
Applying this to calculate An as (A - λ1I)(A - λ2I) Q(A) + kA + sE for An (for n ≥ 2).
④ Theorem 3. The determinant det(A) of a real matrix A of size n × n is equal to the product of its eigenvalues.
○ For example, for a 3 × 3 matrix, the following holds.
○ If A has three linearly independent eigenvectors, det(A) can be shown as follows:
○ If the eigenvalues are λ1, λ2 with multiplicities 1 and 2, respectively, det(A) can be shown as follows:
○ Here, w2 is a generalized eigenvector corresponding to λ2 and v2.
○ In this way, by considering each case, it can be easily shown that the product of the eigenvalues equals det(A).
⑤ Theorem 4. By applying the diagonalization of matrices, A = PDP-1, we can obtain An = PDnP-1
⑥ Theorem 5. For real matrices A and B of size n × n, the eigenvalues of matrix AB are the same as the eigenvalues of matrix BA (ref)
○ Proof: Assume λ is an eigenvalue of AB
⇔ ABv = λv, v ≠ 0
⇔ BABv = BA (Bv) = B · λv = λ (Bv)
⇔ Considering all possible cases as follows, the eigenvalues of BA are the same as those of AB
○ When Bv ≠ 0: λ is an eigenvalue of BA
○ When Bv = 0
⇔ ABv = A0 = 0 = λv
⇔ λ = 0 is an eigenvalue of AB
⇔ 0 = det(AB) = det(A) × det(B) = det(BA)
⇔ Hence, there exists v’ ≠ 0 such that BAv’ = 0
⇔ λ = 0 is an eigenvalue of BA
○ Advanced: #{Eigen(Pn×nvn×1w1×nQn×n)} = #{Eigen(w1×nQn×nPn×nvn×1)} = 1, rank = 1
⑦ Theorem 6. For a real matrix A of size m × n, the nonzero eigenvalues of the matrices AAT and ATA are identical.
○ Related to Theorem 5.
⑧ Theorem 7. Kronecker product
○ For example, given matrix J ∈ ℝn×n, A ∈ ℝm×m, M = J ⊗ A ∈ ℝnm×nm can be defined as follows:
○ Theorem 7-1. Basic Operational Rules
○ Theorem 7-2. (A ⊗ B)T = AT ⊗ BT: this can be understood intuitively.
○ Theorem 7-3. Multiplication rule for the Kronecker product: (A ⊗ B)(C ⊗ D) = (AC) ⊗ (BD)
○ For example, letting J = u·vT leads to (u ⊗ I)(vT ⊗ A) = (u·vT) ⊗ (I · A) = J ⊗ A = M.
○ Theorem 7-4. rank(M) = rank(J ⊗ A) = rank(J) × rank(A)
○ Memorization tip. Because the Kronecker product multiplies components, its properties also tend to appear in multiplicative form.
○ Proof.
○ Let J ∈ ℝn×n, A ∈ ℝm×m, and r = rank(J), s = rank(A). Then we obtain the following (by Theorems 7-1 and 7-3).
○ Since M can be written as a sum of r·s rank-one vectors, the maximum possible value of rank(M) is r·s.
○ In fact, those vectors are linearly independent, so the rank of (M) is exactly r·s.
○ Theorem 7-5. The eigenvalues of M = J ⊗ A are all pairwise products of eigenvalues of J and eigenvalues of A.
○ Theorem 7-6. If x is an eigenvector of J and y is an eigenvector of A, then x ⊗ y is an eigenvector of M = J ⊗ A.
○ Proof.
⑨ Theorem 8. Stable
○ A square matrix A is defined to be stable if all of its eigenvalues have absolute value less than 1, since in that case A∞ = 0.
○ In this case, there exists K < ∞, 0 < α < 1 such that (Aj)pq ≤ Kαj ∀p, q.
⑩ Application 1. Hückel approximation and Hamiltonian
⑪ Python code (cf. WolframAlpha)
○ Using numpy
import numpy as np
matrix = np.array([
[4.56, 10.2, 7.68, 13.68],
[10.2, 33.2, 20.2, 24.8],
[7.68, 20.2, 17.84, 23.44],
[13.68, 24.8, 23.44, 45.55]
])
eigenvalues, eigenvectors = np.linalg.eigh(matrix)
sorted_indices = np.argsort(eigenvalues)[::-1]
sorted_eigenvalues = eigenvalues[sorted_indices]
sorted_eigenvectors = eigenvectors[:, sorted_indices]
print("Eigenvalues:\n", sorted_eigenvalues)
print("\nEigenvectors:\n", sorted_eigenvectors)
○ Using sympy
from sympy import Matrix
# Create SymPy matrix
matrix = Matrix([
[4.56, 10.2, 7.68, 13.68],
[10.2, 33.2, 20.2, 24.8],
[7.68, 20.2, 17.84, 23.44],
[13.68, 24.8, 23.44, 45.55]
])
# Calculate eigenvaleus and eigenvectors
eigenvalues = matrix.eigenvals() # 고유값 계산
eigenvectors = matrix.eigenvects() # 고유벡터 계산
# Output
print("Eigenvalues:")
for eigval, multiplicity in eigenvalues.items():
print(f"Value: {eigval}, Multiplicity: {multiplicity}")
print("\nEigenvectors:")
for eigval, eigen_mult, eigvecs in eigenvectors:
print(f"Eigenvalue: {eigval}")
for vec in eigvecs:
print(f"Eigenvector: {vec}")
⑵ Generalized eigenvectors
① Overview
○ Definition: When the geometric multiplicity of an asymmetric matrix is less than the algebraic multiplicity, vectors that replace the lacking eigenvectors
○ The generalized eigenvectors of matrix A of rank m are as follows
○ (A - λI)mxm = 0 & (A - λI)m-1xm ≠ 0
○ When m = 1, it is the same as the definition of eigenvector.
○ Used in Jordan canonical form.
② Example 1. The eigenvalue of the following matrix A is 1, and the corresponding eigenvector is v1 = (1, 0)T
○ The algebraic multiplicity of eigenvalue 1 is 2, and the geometric multiplicity is 1.
○ (A - λI)2 v2 = (A - λI) {(A - λI) v2} = 0 ⇔ (A - λI) v2 = v1
○ v2 = (*, 1)T (e.g., (0, 1)T) that satisfies (A - I)v2 = (1, 0)T is called a generalized eigenvector.
③ Example 2. Ref
⑶ Eigenfunctions
① Theorem of Sturm-Liouville: Different eigenfunctions are orthogonal to each other
2. Diagonalization of Matrices
⑴ Diagonalization of Matrices
① Diagonal Matrix
○ An n × n matrix where all elements except the diagonal are zero
○ Property 1. The determinant is the product of the diagonal elements
○ Property 2. The inverse matrix has the reciprocal of each diagonal element of the given diagonal matrix
② Diagonalizability
○ Definition: A matrix A is diagonalizable if there exist a diagonal matrix D and an invertible matrix P satisfying the following
○ Orthogonal Diagonalization: For a matrix P composed of orthonormal basis vectors.
○ Theorem 1. The necessary and sufficient condition for an $n \times n$ matrix $A$ to be diagonalizable is that $A$ has $n$ linearly independent eigenvectors.
○ Theorem 2. If an $n \times n$ matrix $A$ has $n$ distinct eigenvalues λ1, λ2, ···, λn, it can be diagonalized
○ If $P$ is a matrix having linearly independent eigenvectors of $A$ as columns, $D$ is as follows:
○ Theorem 3. Spectral Theorem: An $n \times n$ matrix $A$ can be orthogonally diagonalized if and only if $A$ is a symmetric matrix.
○ Theorem 4. Generalized eigenvectors of an $n \times n$ matrix $A$ always span ℝn, thus such a matrix $A$ can be diagonalized.
○ Example: $n \times n$ matrix $A$ satisfying A2 = A has eigenvalues λ = 0, 1 and can be diagonalized.
○ Theorem 5. A matrix is diagonalizable if and only if its minimal polynomial factors into distinct linear factors.
○ Minimal polynomial: the minimal polynomial of $A$ is the nonzero polynomial $p$ of least degree such that $p(A)=O$ (the zero matrix).
○ The minimal polynomial is the greatest common divisor (gcd) of all polynomials $q$ such that $q(A)=O$.
○ Theorem 6. If $D$ is a diagonal matrix with three distinct diagonal entries, then any matrix that commutes with $D$ must also be diagonal, and this diagonal matrix shares the same invertible matrix $P$ as $D$. Here, “commute” means satisfying $AB = BA$.
○ Theorem 7. If $M$ is diagonalizable, then $\log \det M = \operatorname{Tr}(\log M).$
M = PDP-1
det M = λ1λ2 ··· λn ⇒ log det M = ∑i log λi = Tr(log D) = Tr(log DP-1P) = Tr(log PDP-1) = Tr(log M)
③ Examples
○ Given matrix $A$
○ Calculate eigenvalues and eigenvectors
○ Calculate $P$ and $D$
⑵ Block Diagonalization of Matrices
① Block Diagonal Matrix
○ Definition: When Ai ∈ ℳni,ni (F) and n1 + ··· + nk = n, the matrix A in the following form
○ Properties: When Ai, Bi ∈ ℳni,ni (F),
○ Property 1. diag(A1, ···, Ak)·diag(B1, ···, Bk) = diag(A1B1, ···, AkBk)
○ Property 2. If Ai is invertible, (diag(A1, ···, Ak))-1 = diag(A1-1, ···, Ak-1)
② Jordan Canonical Form
○ When a matrix can’t be diagonalized, but there are still generalized eigenvectors corresponding to the eigenvalues, it can be transformed into the Jordan canonical form
○ Jordan Canonical Form: A = PJP-1 (where J is not a complete diagonal matrix, but a matrix composed of Jordan blocks)
○ Theorem 1. If Ak = 0 (nilpotent), considering the Jordan form of the matrix A, A becomes a block diagonal matrix consisting of suitable Ak matrices.
○ Theorem 2. If $A$ is diagonalizable and $B$ commutes with $A$ (i.e., $AB=BA$), then $B$ can be represented as a block-diagonal matrix, where each block corresponds to an eigenvalue of $A$.
○ Proof. If $Av=\lambda v$, then $A(Bv)=B(Av)=\lambda(Bv),$ so $Bv$ lies in the same eigenspace of $A$ as $v$. Hence, $B$ must preserve each eigenspace of $A$, which implies that $B$ is block-diagonal with respect to the decomposition into eigenspaces.
3. Quadratic Forms
⑴ Overview
① Definition: 4x12 + 2x1x2 + 3x22 is a quadratic form, but 4x12 + 2x1 is not a quadratic form.
② Representation using a symmetric matrix
③ \forall M,\quad x^{T}Mx = x^{T}\left(\frac{M+M^{T}}{2}\right)x \quad\left(\because\ x^{T}\left(\frac{M-M^{T}}{2}\right)x=0\ \text{(anti-symmetric)}\right)
⑵ Definition of signs of quadratic forms: For a symmetric matrix A ∈ ℳn and any vector x ≠ 0 on ℝn
① Positive definite matrix (PD)
○ All eigenvalues of A are greater than 0 $\iff Q(\mathbf{x}) \succ 0 \quad \forall \mathbf{x} \neq \mathbf{0} \iff \mathbf{x}^{\mathsf{T}} A \mathbf{x} = \mathbf{x}^{\mathsf{T}}(\lambda \mathbf{x}) = \lambda \left|\mathbf{x}\right|^2 > 0$
○ $iff$ All $n$ leading principal minors are positive.
○ $iff$ There exists a factorization $A=B^{T}B$ with $B$ square and nonsingular.
② Positive semi-definite matrix (PSD)
○ All eigenvalues of A are greater than or equal to 0 $\iff Q(\mathbf{x}) \succeq 0 \quad \forall \mathbf{x} \neq \mathbf{0} \iff \mathbf{x}^{\mathsf{T}} A \mathbf{x} = \mathbf{x}^{\mathsf{T}}(\lambda \mathbf{x}) = \lambda \left|\mathbf{x}\right|^2 \geq 0$
○ $\iff$ All $2^n - 1$ principal minors are non-negative. An example of principal minor is as follows:
○ $\iff$ There exists a factorization $A=B^{T}B$
③ Negative definite matrix (ND)
○ All eigenvalues of A are less than 0 $\iff Q(\mathbf{x}) \prec 0 \quad \forall \mathbf{x} \neq \mathbf{0} \iff \mathbf{x}^{\mathsf{T}} A \mathbf{x} = \mathbf{x}^{\mathsf{T}}(\lambda \mathbf{x}) = \lambda \left|\mathbf{x}\right|^2 < 0$
④ Negative semi-definite matrix (NSD)
○ All eigenvalues of A are less than or equal to 0 $\iff Q(\mathbf{x}) \preceq 0 \quad \forall \mathbf{x} \neq \mathbf{0} \iff \mathbf{x}^{\mathsf{T}} A \mathbf{x} = \mathbf{x}^{\mathsf{T}}(\lambda \mathbf{x}) = \lambda \left|\mathbf{x}\right|^2 \leq 0$
⑤ Indefinite matrix
○ When the signs of the eigenvalues are not uniform, unlike ① to ④
⑶ Determination of the signs of quadratic forms: For a symmetric matrix A ∈ ℳn and a subset S ={i1, i2, ···, ik} of {1, 2, ···, n}
① Principal submatrix: A k × k matrix formed by selecting the rows and columns of A corresponding to S
② Leading principal submatrix: A k × k matrix obtained by omitting the last n-k row and column vectors of A
③ Theorem 1. A symmetric matrix A ∈ ℳn being positive definite is equivalent to sgn(det(Ak)) = 1, k = 1, 2, ···, n
④ Theorem 2. A symmetric matrix A ∈ ℳn being negative definite is equivalent to sgn(det(Ak)) = (-1)k, k = 1, 2, ···, n
⑤ Theorem 3. A symmetric matrix A ∈ ℳn being positive semi-definite is equivalent to all principal submatrix determinants being non-negative
○ If any leading principal submatrix determinant is 0 while attempting Theorem 1 or 2, try Theorem 3
○ Obviously, if the sign of any leading principal submatrix determinant changes, there is no need to attempt Theorem 3 or 4 as it indicates an indefinite matrix
⑥ Theorem 4. A symmetric matrix A ∈ ℳn being negative semi-definite is equivalent to all principal submatrix determinants of -A being non-negative
○ If the sign of any principal submatrix determinant is not uniform while attempting Theorem 3, try Theorem 4
⑦ sgn indicates 1 for positive values and -1 for negative values when the determinant is directly calculated
⑷ For a C2 function f: Ω → ℝ defined on a region Ω ⊂ ℝn, if at point p ∈ Ω, ∇f(p) = 0, then the following holds
① If $H_f$(p) is a positive definite matrix, then f has a local minimum at point x = p
② If $H_f$(p) is a negative definite matrix, then f has a local maximum at point x = p
③ If $H_f$(p) is an indefinite matrix, then point x = p is a saddle point of f
④ If $H_f$(p) is a positive semi-definite matrix, then f has a relative minimum at point x = p
⑤ If $H_f$(p) is a negative semi-definite matrix, then f has a relative maximum at point x = p
⑸ Determining the sign of a constrained quadratic form: For symmetric matrices $A$ ∈ ℳ𝑛 and $B$ ∈ ℳ𝑚,𝑛 (with $n$ > $m$), given a $n$-dimensional quadratic form $Q_A$(x) = xT$A$x with the linear constraint {x ∈ ℝ𝑛 $\mid$ Bx = 0}, the following statements hold when defining a new $(m+n)$ × $(m+n)$ matrix H as below.
① Theorem 1. If sgn($\left|H_{m+i}\right|$) = $(-1)^m, i = m+1, m+2, ···, n$, then $Q_A$(x) > 0 holds
○ Keep in mind it is not a necessary and sufficient condition
② Theorem 2. If sgn($\left|H_{m+i}\right|$) = $(-1)^i, i = m+1, m+2, ···, n$, then $Q_A$(x) < 0 holds
○ Keep in mind it is not a necessary and sufficient condition
③ Example: The following example observes a negative definite symmetric matrix A
④ Even a quadratic form without a sign may have a sign under certain constraints
⑹ Applications of quadratic forms
① Theorem 1.
○ Proof: Since a symmetric matrix A can be orthogonally diagonalizable (∵ spectral theorem)
\[M \succ 0 \iff T^{\mathsf{T}}MT \succ 0.\]② Theorem 2. Congruence transformation: If $T$ is nonsingular, then
③ Theorem 3. Schur complement formula
④ Theorem 4. S-procedure
○ S-lemma ($k = 1$): A necessary and sufficient condition under Slater’s condition.
○ Conservative relaxation of the S-procedure ($k$ ≥ 2): Only a sufficient condition holds, as shown above.
○ Generalized S-procedure: A polynomial version of S-procedure
⑤ Theorem 5. Semidefinite programming (SDP) for continuous hybrid system
⑥ Theorem 6. Semidefinite programming (SDP) for discrete hybrid system
⑦ Theorem 7. A polynomial $p$ is sum of squares. ⇔ ∃𝑄 ≽ 0 s.t. $p = z^TQz$, where $z$ is a vector of monomials.
Input: 2020.05.19 23:48
Modified: 2024.11.12 09:45