Eigenvectors and Eigenvalues (vector riêng/đặc trưng và giá trị riêng/đặc trưng)

Note lại 1 số kiến thức nền về đại số tuyến tính có liên quan đến đủ mọi thứ như SVD, PCA, optimization ... (không đầy đủ, xem thêm trong các tài liệu khác).

Linear Algebra MIT OCW

Đại số tuyến tính TS.Mỵ Vinh Quang, 2004

Trị riêng và vector riêng

Singular Value Decomposition Tutorial

Introduction to the Singular Value Decomposition
...

Tiếp theo phần Vectors và Matrices

Eigenvectors and Eigenvalues (vector riêng/đặc trưng và giá trị riêng/đặc trưng)

Cho A là ma trận vuông cấp n trên trường F (F= ℝ; ℂ). Một số \(\lambda  \in F\)(scalar) được gọi là giá trị riêng (hay gọi tắt là trị riêng) của ma trận A nếu tồn tại một vector \(x \in {F^n},x \ne 0\) sao cho \(Ax = \lambda x\).

Nếu \(x = ({x_1},{x_2}, \ldots ,{x_n})\) là vector riêng của ma trận A với trị riêng \(\lambda \) thì với mọi số vô hướng \(\alpha  \ne 0\), \(\alpha x\) cũng là vector riêng của A ứng với trị riêng \(\lambda \). Tất cả các vector riêng có cùng giá trị riêng cùng vector 0, tạo thành một không gian riêng (eigenspace) ký hiệu là \({E_\lambda }\). Hay\({E_\lambda }\)là không gian nghiệm (nullspace) của phương trình \((A - \lambda I)x = 0\) (hệ phương trình tuyến tính thuần nhất). \({E_\lambda }\) là không gian con của \({F^n}\).

Tính chất:

§  \(\lambda \) chính là nghiệm của phương trình \({p_A}\left( z \right) = \det \left( {A - zI} \right) = 0\) gọi là phương trình đặc trưng của ma trận A. \({p_A}\left( z \right) = {\rm{det}}\left( {A - zI} \right)\) gọi là đa thức đặc trưng của ma trận A.

§  Một giá trị riêng có thể ứng với nhiều vector riêng (do\(x \ne 0\)nên hệ phương trình thuần nhất có một nghiệm khác 0, có nghĩa hệ có vô số nghiệm)

§  Mỗi vector riêng chỉ ứng với một giá trị riêng duy nhất

§  Ma trận A là nghiệm của đa thức đặc trưng của chính nó (trong trường hợp này đa thức đặc trưng được coi là đa thức ma trận, nghĩa là biến số của nó không phải là biến số thực mà là biến ma trận).

§  Nếu \(\lambda  = 0\) là giá trị riêng của ma trận A thì A không khả nghịch. Ngược lại, nếu mọi giá trị riêng của A đều khác không thì A khả nghịch.

§  Nếu \(\lambda \) là giá trị riêng của A thì\({\lambda ^k}\) là giá trị riêng của \({A^k}\).

Ví dụ về eigenvectors và eigenvalues:

Một biến đổi tuyến tính (linear transformation) \(T({x_1},{x_2}) = (5{x_1},15{x_2})\) có ý nghĩa hình học đơn giản dễ thấy: kéo dãn (stretch) 5 lần theo chiều \({x_1}\)(\({x_1} - direction\)) và 15 lần theo chiều \({x_2}\).

Ngược lại \(T({x_1},{x_2}) = (13{x_1}\; - {\rm{ }}4{x_2}, - {\rm{ }}4{x_1}\; + {\rm{ }}7{x_2})\) không có ý nghĩa hình học đơn giản như ví dụ trên.

Tuy nhiên bằng cách sử dụng hai vector cơ sở (basic vectors) $v_1=\left( 1,2 \right),v_2=\left( -2,1 \right)$:

$T(v_1)=\left( 13(1)-4(2),-4(1)+7(2) \right)=\left( 5,10 \right)=5v_1$$T(v_2)=\left( 13\left( -2 \right)-4(1),-4\left( -2 \right)+7(1) \right)=\left( -30,15 \right)=15v_2$

Có nghĩa phép biến đổi T có ý nghĩa hình học đơn giản là kéo dãn 5 lần theo \({v_1} - direction\) và 15 lần theo \({v_2} - direction\). Có thể thấy $v_1=\left( 1,2 \right),v_2=\left( -2,1 \right)$ chính là các eigenvectors của T tương ứng với các eigenvalues là \({\lambda _1} = 5,{\lambda _2} = 15\) (WolframAlpha “eigenvectors {{13,-4},{-4,7}}”)

Characteristic Polynomial (đa thức đặc trưng)

Đa thức bậc n của biến z gọi là đa thức đặc trưng của ma trận A là đa thức ký hiệu \({p_A}\left( z \right)\) hay \({P_A}\left( z \right)\) được định nghĩa như sau: \({p_A}\left( z \right) = {\rm{det}}\left( {A - zI} \right)\).

§  Các nghiệm của đa thức đặc trưng gọi là giá trị riêng của ma trận A

§  Nếu \(\lambda \) là một giá trị riêng của A thì \(det(A - \lambda I) = 0\) do đó hệ phương trình thuần nhất

\(\left( {A - \lambda I} \right)\left[ {\begin{array}{*{20}{c}}{{x_1}}\\ \vdots \\{{x_n}}\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}0\\ \vdots \\0\end{array}} \right]\)

 có vô số nghiệm. Không gian nghiệm của phương trình trên gọi là không gian con riêng của ma trận A ứng với giá trị riêng \(\lambda \). Các vector khác không là nghiệm của phương trình trên gọi là các vector riêng của ma trận A ứng với giá trị riêng \(\lambda \), tạo thành một cơ sở của không gian riêng gọi là các vector riêng độc lập tuyến tính với giá trị riêng \(\lambda \).

Định lý:

Vô hướng \(\lambda \) là giá trị riêng của A khi và chỉ khi \({p_A}\left( \lambda  \right) = 0\)

Chứng minh:

Số \(\lambda \) là giá trị riêng của A khi và chỉ khi tồn tại một vector \(x \in {F^n},x \ne 0\) sao cho \(Ax = \lambda x\). Khi đó hệ phương trình tuyến tính \((A - \lambda I)x = 0\) có nghiệm \(x \ne 0\) hay tương đương hệ phương trình có vô số nghiệm \( \Leftrightarrow det(A - \lambda I) = 0\).

Ví dụ: tìm đa thức đặc trưng, vector riêng và giá trị riêng của ma trận

\(A = \left[ {\begin{array}{*{20}{c}}0\\1\\1\end{array}\begin{array}{*{20}{c}}1\\0\\1\end{array}\begin{array}{*{20}{c}}1\\1\\0\end{array}} \right]\)

Đa thức đặc trưng của ma trận A \({p_A}(\lambda ) = \left[ {\begin{array}{*{20}{c}}{ - \lambda }\\1\\1\end{array}\begin{array}{*{20}{c}}1\\{ - \lambda }\\1\end{array}\begin{array}{*{20}{c}}1\\1\\{ - \lambda }\end{array}} \right] =  - {\lambda ^3} + 3\lambda  + 2\)

${{p}_{A}}(\lambda )=0\Leftrightarrow {{(\lambda +1)}^{2}}(2-\lambda )=0\Leftrightarrow \lambda =-1\vee \lambda =2$

Ma trận A có hai giá trị riêng là \(\lambda  =  - 1\) và \(\lambda  = 2\)

Tìm trị vector riêng của A

§  Với \(\lambda  =  - 1\) hệ \(\left[ {\begin{array}{*{20}{c}}1\\1\\1\end{array}\begin{array}{*{20}{c}}1\\1\\1\end{array}\begin{array}{*{20}{c}}1\\1\\1\end{array}\left| {\begin{array}{*{20}{c}}0\\0\\0\end{array}} \right.} \right]\) có vô số nghiệm phụ thuộc hai tham số \({x_2},{x_3}\).

Nghiệm tổng quát là

\({x_1} =  - a - b,{x_2} = a,{x_3} = b\). Không gian con riêng của A ứng với giá trị riêng \(\lambda  =  - 1\) là \({E_{ - 1}} = \{ ( - a - b,a,b)|a,b \in R\} \) là tất cả các vector có dạng \(( - a - b,a,b)\) với \({a^2} + {b^2} \ne 0\) (vì vector riêng phải khác 0). Như vậy \(\dim E( - 1) = 2\) và A có 2 vector riêng độc lập tuyến tính ứng với giá trị riêng \(\lambda  =  - 1\) là \({\alpha _1} = ( - 1,1,0),{\alpha _2} = ( - 1,0,1)\)

§  Với \(\lambda  = 2\) hệ \(\left[ {\begin{array}{*{20}{c}}{ - 2}\\1\\1\end{array}\begin{array}{*{20}{c}}1\\{ - 2}\\1\end{array}\begin{array}{*{20}{c}}1\\1\\{ - 2}\end{array}\left| {\begin{array}{*{20}{c}}0\\0\\0\end{array}} \right.} \right]\mathop  \to \limits^{(1) \mathbin{\lower.3ex\hbox{$\buildrel\textstyle\rightarrow\over{\smash{\leftarrow}\vphantom{_{\vbox to.5ex{\vss}}}}$}} (3)} \left[ {\begin{array}{*{20}{c}}1\\1\\{ - 2}\end{array}\begin{array}{*{20}{c}}1\\{ - 2}\\1\end{array}\begin{array}{*{20}{c}}{ - 2}\\1\\1\end{array}\left| {\begin{array}{*{20}{c}}0\\0\\0\end{array}} \right.} \right]\mathop  \to \limits^{\scriptstyle(2) = (2) - 1\atop\scriptstyle(3) = (3) + 2*(2)} \left[ {\begin{array}{*{20}{c}}1\\0\\0\end{array}\begin{array}{*{20}{c}}1\\{ - 3}\\{ - 3}\end{array}\begin{array}{*{20}{c}}{ - 2}\\3\\3\end{array}\left| {\begin{array}{*{20}{c}}0\\0\\0\end{array}} \right.} \right] \to \left[ {\begin{array}{*{20}{c}}1\\0\\0\end{array}\begin{array}{*{20}{c}}1\\{ - 3}\\0\end{array}\begin{array}{*{20}{c}}{ - 2}\\3\\0\end{array}\left| {\begin{array}{*{20}{c}}0\\0\\0\end{array}} \right.} \right]\) có vô số nghiệm phụ thuộc tham số \({x_3}\). Nghiệm tổng quát là \({x_1} = a,{x_2} = a,{x_3} = a\). Không gian con riêng của A ứng với giá trị riêng \(\lambda  = 2\) là \({E_2} = \{ (a,a,a)|a \in R\} \) là tất cả các vector có dạng \((a,a,a)\) với \(a \ne 0\) (vì vector riêng phải khác 0). Như vậy \(\dim E(2) = 1\)và A có 1 vector riêng độc lập tuyến tính ứng với giá trị riêng \(\lambda  = 2\) là \({\alpha _3} = (1,1,1)\).

§  Với cả hai trường hợp A có 3 vector riêng độc lập tuyến tính là \({\alpha _1} = ( - 1,1,0),{\alpha _2} = ( - 1,0,1),{\alpha _3} = (1,1,1)\)

Do \({p_A}\left( z \right)\)là đa thức nên theo Định lý cơ bản của đại số (Fundamental theorem of algebra) mọi đa thức một biến có số nghiệm phức bằng bậc của nó, nếu mỗi nghiệm được tính với số bội của nó. Khi đó

\({p_A}\left( z \right) = (z - {\lambda _1})(z - {\lambda _2})...(z - {\lambda _n})\)

với  \({\lambda _i} \in C\) (trường số phức). Như vậy ma trận A trên trường số thực có thể có giá trị riêng ảo.

Algebraic Multiplicity (Vô số/hệ số đại số)

Nếu giá trị riêng \({\lambda _i}\) xuất hiện k lần trong biểu diễn đa thức \({p_A}\left( z \right)\) trên thì gọi \({\lambda _i}\) là giá trị riêng bội k của A. Với k = 1 thì \({\lambda _i}\) gọi là giá trị riêng đơn. Khi đó số lần lặp lại k của giá trị riêng \({\lambda _i}\) được gọi là vô số/hệ số đại số (algebraic multiplicity) của \({\lambda _i}\) ký hiệu là \(AM({\lambda _i})\) hay \({\mu _A}({\lambda _i})\).

Hệ số đại số của giá trị riêng luôn lớn hơn hay bằng hệ số hình học hay $dimE({{\lambda }_{i}})\le k$.

§  Nếu \({\mu _A}({\lambda _i}) = 1\) khi đó\({\lambda _i}\) gọi là giá trị riêng đơn (simple eigenvalue).

§  Nếu \({\mu _A}({\lambda _i}) = {\gamma _A}({\lambda _i})\)khi đó \({\lambda _i}\) gọi là semisimple eigenvalue (xem Geometric Multiplicity)

Geometric Multiplicity (Vô số/hệ số hình học)

Số chiều của không gian riêng \({E_\lambda }\) tương ứng $dimE(\lambda )$ hay chính là số vector riêng độc lập tuyến tính ứng với  giá trị riêng \({\lambda _i}\) gọi là vô số/hệ số hình học (geometric multiplicity) của \({\lambda _i}\) ký hiệu là \(GM({\lambda _i})\) hay \({\gamma _A}({\lambda _i})\). Nếu \(\lambda \) và \(\lambda \prime \) là hai giá trị riêng khác nhau thì \({E_\lambda } \cap {E_{\lambda \prime }} = \{ 0\} \).

Similarity Transformation (biến đổi đồng dạng/tương đương)

Hai ma trận vuông A và B cấp n gọi là đồng dạng với nhau ký hiệu $A \sim B$ nếu tồn tại một ma trận không suy biến (khả nghịch) P sao cho \(B = {P^{ - 1}}AP\). Quan hệ đồng dạng là một quan hệ tương đương.
Ma trận A và B gọi là unitarily similar (có khi còn gọi là unitarily equivalent) nếu $B={{U}^{*}}AU$ với U là unitary.

Ma trận P đại diện cho phép biến đổi ma trận gốc A. Phép biến đổi \(A \mapsto {P^{ - 1}}AP\)gọi là phép biến đổi đồng dạng/tương đương hay sự kết hợp/liên hợp (conjugation) của ma trận A, B gọi là ma trận liên hợp (conjugate matrix) của ma trận A. Hai ma trận đồng dạng (tương đương) có nhiều tính chất:

§  ${{p}_{A}}\left( \lambda \right)={{p}_{B}}\left( \lambda \right)$

§  Cùng trị riêng, các trị riêng có cùng vô số hình học, vô số đại số

§  $det(A)=det(B)$, $rank(A) = rank(B)$, $tr(A) = tr(B)$…

Ví dụ:

Cho\(B = {P^{ - 1}}AP\) là ma trận đồng dạng với ma trận A.

\(det(B - \lambda {I_n}) = det({P^{ - 1}}AP - \lambda {I_n}) = \det ({P^{ - 1}}AP - \lambda {P^{ - 1}}{I_n}P)\)

\( = \det ({P^{ - 1}}(A - \lambda {I_n})P) = \det ({P^{ - 1}})\det (A - \lambda {I_n})\det (P) = \det (A - \lambda {I_n})\)

Eigenvalue Decomposition (phân tích giá trị riêng)

Cho \({\lambda _1},{\lambda _2},...,{\lambda _n}\) là các giá trị riêng của ma trận A và \({x_1},{x_2},...,{x_n}\) là các vector riêng tương ứng. Gọi \({\Lambda _{nxn}}\) là ma trận chéo n×n được tạo thành bởi \({\lambda _j}\) và X là ma trận cột được tạo thành từ các vector riêng (cột thứ j của X là vector \({x_j}\) viết ở dạng cột). Khi đó do \(A{x_j} = \lambda {x_j}\):

$\left[ A \right]=\left[ {{x}_{1}}\left| {{x}_{2}}\left| ... \right.\left| {{x}_{n}} \right. \right. \right]=\left[ {{x}_{1}}\left| {{x}_{2}}\left| ... \right.\left| {{x}_{n}} \right. \right. \right]\left[ \begin{matrix}
{{\lambda }_{1}} & {} & {} \\
{} & \ddots & {} \\
{} & {} & {{\lambda }_{n}} \\ \end{matrix} \right]$

\(AX = X\Lambda \)

Giả định A có n vector độc lập tuyến tính với nhau, thì X khả nghịch tồn tại \({X^{ - 1}}\) và:

\(A = X\Lambda {X^{ - 1}}\)

Cách viết này được gọi là phân tích giá trị riêng (eigenvalue decomposition) của ma trận A.

Diagonalizability (khả năng chéo hóa được)

Cho A là ma trận vuông cấp n, ma trận A chéo hóa được nếu tồn tại một ma trận P là ma trận vuông cấp n không suy biến (khả nghịch) sao cho \(B = {P^{ - 1}}AP\) là ma trận chéo (lưu ý lúc này \(A = PB{P^{ - 1}}\)).

Chéo hóa ma trận A là tìm ma trận P vuông cấp n sao cho \(B = {P^{ - 1}}AP\) là ma trận chéo.

Nếu chéo hóa được ma trận A thì việc thao tác/nghiên cứu các tính chất trên A có thể đưa về việc thao tác/nghiên cứu các tính chất trên một ma trận chéo dễ dàng hơn.

Định lý: (điều kiện cần và đủ để một ma trận vuông chéo hóa được)

Ma trận A vuông cấp n chéo hóa được khi và chỉ khi A có đủ n vector riêng độc lập tuyến tính và \(\sum\limits_{i = 1}^k {{\rm{dimE}}({\lambda _i})}  = n\) trong đó \({\lambda _i}\) là tất cả các giá trị riêng của A.

Nếu ma trận A vuông cấp n có n trị riêng phân biệt (distinct eigenvalues) trong trường F thì sẽ chéo hóa được trên trường F (không có chiều ngược lại). Có n trị riêng phân biệt tương đương mọi giá trị riêng của A đều có vô số/hệ số đại số bằng vô số/hệ số hình học.

Lưu ý: ma trận đơn vị \(A = diag(1,1)\) đã là ma trận chéo chỉ có eigenvalue \(\lambda  = 1\) ứng với hai eigenvectors \({v_1} = (0,1),{v_2} = (1,0)\).

Nếu A chéo hóa được thì ma trận P cần tìm là ma trận cột có các cột là các vector riêng độc lập tuyến tính của A viết theo cột.

Ví dụ:

\(A = \left[ {\begin{array}{*{20}{c}}0\\1\\1\end{array}\begin{array}{*{20}{c}}1\\0\\1\end{array}\begin{array}{*{20}{c}}1\\1\\0\end{array}} \right]\)có 2 giá trị riêng \({\lambda _1} =  - 1,{\lambda _2} = 2\) (lưu ý \({\lambda _1}\)có vô số/hệ số đại số là 2) và 3 vector riêng độc lập tuyến tính \({\alpha _1} = ( - 1,1,0),{\alpha _2} = ( - 1,0,1),{\alpha _3} = (1,1,1)\).

Ma trận P cần tìm: \(P = \left[ {{\alpha _1}\left| {{\alpha _2}} \right.\left| {{\alpha _3}} \right.} \right] = \left[ {\begin{array}{*{20}{c}}{ - 1}\\1\\0\end{array}\begin{array}{*{20}{c}}{ - 1}\\0\\1\end{array}\begin{array}{*{20}{c}}1\\1\\1\end{array}} \right]\)

Ma trận chéo\(B = {P^{ - 1}}AP = \left[ {\begin{array}{*{20}{c}}{ - 1}\\0\\0\end{array}\begin{array}{*{20}{c}}0\\{ - 1}\\0\end{array}\begin{array}{*{20}{c}}0\\0\\2\end{array}} \right]\)

Ví dụ khác ứng dụng tính lũy thừa n của ma trận \(A = \left[ {\begin{array}{*{20}{c}}1&{ - 1}\\2&4\end{array}} \right]\)

Tìm trị riêng và vector riêng của A \({p_A}(\lambda ) = 0 \Leftrightarrow (\lambda  - 2)(\lambda  - 3) = 0 \Leftrightarrow \lambda  = 2 \vee \lambda  = 3\)

Các vector riêng \({\alpha _1} = [1, - 1],{\alpha _2} = [1, - 2]\)

Ma trận làm chéo hóa P: \(P = \left[ {\begin{array}{*{20}{c}}1&1\\{ - 1}&{ - 2}\end{array}} \right]\)

${{P}^{-1}}=\left[ \begin{matrix}
2 & 1 \\
-1 & -1 \\
\end{matrix} \right]$

Chéo hóa \({P^{ - 1}}AP = \left[ {\begin{array}{*{20}{c}}2&1\\{ - 1}&{ - 1}\end{array}} \right]\left[ {\begin{array}{*{20}{c}}1&{ - 1}\\2&4\end{array}} \right]\left[ {\begin{array}{*{20}{c}}1&1\\{ - 1}&{ - 2}\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}2&0\\0&3\end{array}} \right]\)

Chứng minh được $A^n=PB^nP^{-1}$:
${{({{P}^{-1}}AP)}^{2}}=({{P}^{-1}}AP)({{P}^{-1}}AP)={{P}^{-1}}{{A}^{2}}P$
${{({{P}^{-1}}AP)}^{3}}=({{P}^{-1}}AP)({{P}^{-1}}{{A}^{2}}P)={{P}^{-1}}{{A}^{3}}P$

Do đó:

${{B}^{n}}={{({{P}^{-1}}AP)}^{n}}={{P}^{-1}}{{A}^{n}}P=\left[ \begin{matrix}
{{2}^{n}} & 0 \\
0 & {{3}^{n}} \\
\end{matrix} \right]$

${{A}^{n}}=P\left[ \begin{matrix}
{{2}^{n}} & 0 \\
0 & {{3}^{n}} \\
\end{matrix} \right]{{P}^{-1}}=\left[ \begin{matrix}
{{2}^{n+1}}-{{3}^{n}} & {{2}^{n}}-{{3}^{n}} \\
-2({{2}^{n}}-{{3}^{n}}) & -{{2}^{n}}+{{2.3}^{n}} \\ \end{matrix} \right]$

Matrix Decomposition (phân tích/triển khai ma trận)

Phân tích/triển khai/khai triển ma trận (matrix decomposition) hay ma trận nhân tử (matrix factorization) là thực hiện phân tích thừa số/ nhân tử hóa (factorization) của một ma trận thành tích của nhiều ma trận. Có nhiều loại phân tích ma trận khác nhau. Một số các phân tích ma trận dựa trên giá trị riêng và vector riêng có thể kể đến như sau:

§  Eigenvalue decomposition (phân tích giá trị riêng)

§  Jordan decomposition

§  Schur decomposition

§  Singular value decomposition (SVD - phân tích giá trị kỳ dị/đặc biệt/đơn)

§  …