Archive

Posts Tagged ‘Matrix Theory’

Dạng Frobenius

March 16, 2010 Leave a comment

Trên trường phức giả sử là một khối Jordan cấp ứng với giá trị riêng , trong phân tích Jordan của một ma trận

Giả sử là vector cyclic ứng với thế thì là vector cyclic ứng với

Đặt .

Dễ thấy

Đặt

Khi đó


Xét

là không gian con bất biến qua (xét trên trường thực)

Chứng minh được là cơ sở của

Hạn chế của ánh xạ tuyến tính ứng với xuống có ma trận trong có dạng ma trận khối

Trong đó , và các khối khác thì bằng ma trận

Đồng chéo hóa hai ma trận

March 16, 2010 4 comments

Trong bài trước tôi có nhắc đến giải thuật Jacobi cho bài toán chéo hóa. Bây giờ ta tiếp tục đề cập đến bài toán tương tự cho vấn đề đồng chéo hóa hai ma trận về góc độ lý thuyết lẫn phương pháp xấp xỉ.

Đầu tiên chúng ta cần chú ý một tính chất quan trọng của ma trận xác định dương.

Định lý 1. (Phân tích Cholesky)

Giả sử là ma trận Hermite xác định dương, khi đó tồn tại duy nhất ma trận tam giác dưới có các phần tử trên đường chéo chính đều dương sao cho A=LL^*.

Chứng minh

Ta tìm ma trận
sao cho A=LL^*.

Khi đó

Trong đó với cột đầu tiên

suy ra .

suy ra .

suy ra .

Giả sử tính được cột đầu của , ta tính cột thứ như sau

suy ra

.

suy ra

Ma trận xây dựng như vậy thỏa mãn yêu cầu bài toán.

Bây giờ giả sử tồn tại hai phân tích suy ra là một ma trận đường chéo. Ta có suy ra . Do đó D^2=L_2^{-1}L_2 L_2^* (L_2^*)^{-1}=I suy ra .  Điều này chứng tỏ phân tích Cholesky của ma trận là duy nhất.

Trong Mathematica chúng ta sử dụng lệnh CholeskyDecomposition[m] để tìm phân tích Cholesky của ma trận .

Ví dụ. Tìm phân tích Cholesky của ma trận

Ta làm như nhau

L=CholeskyDecomposition[{{1, 1/2, 1/3, 1/4, 1/5},
{1/2, 1/3, 1/4, 1/5, 1/6}, {1/3, 1/4, 1/5, 1/6, 1/7},
{1/4, 1/5, 1/6, 1/7, 1/8}, {1/5, 1/6, 1/7, 1/8, 1/9}}];
Print["L=",MatrixForm[L]];

Kết quả thu được

Theo ý tưởng chứng minh của định lý bạn cũng có thể tự viết một hàm  tìm phân tích Cholesky xem như bài tập lập trình nhỏ với Mathematica.

Về vấn đề phân tích ma trận, có thể tham khảo thêm ở đây , hay bất kì tài liệu nào về Phương pháp Tính cho Đại số Tuyến tính.

Bây giờ trở lại bài toán đồng chéo hóa.

Định lý 2. Nếu A, B là hai ma trận Hermite và A là xác định dương. Khi đó luôn tồn tại ma trận T sao cho T^* A T=I, và T^* B T có dạng đường chéo.

Chứng minh

Theo Định lý 1, ta xây dựng được phân tích Cholesky của ma trận A=LL^*, hay L^{-1}A(L^*)^{-1}=I. Để ý rằng C= (L^*)^{-1} B L^{-1} cũng Hermite, theo kết quả quen thuộc của bài toán chéo hóa là xây dựng được ma trận unita U sao cho U C U^{*} là ma trận đường chéo. Đặt T=(L^{-1})^*U^{*}, chính là ma trận cần tìm.

(còn tiếp…)

Circulant Matrices

July 17, 2009 Leave a comment

Definition.  Given T:\mathbb{C}^n\to \mathbb{C}^n be a linear operator such that for every x=(x_0,x_2,...,x_{n-1}) then

T(x_0,x_1,...,x_{n-1})=(x_{n-1},x_0,x_1,...,x_{n-2})

The matrix with k-row is given by T^{k-1}x, \ k=1,2,...,n will be called circulant and denoted by X=circ(x)=circ(x_0,x_1,...,x_n)

X=\begin{pmatrix}x_0 & x_1 & ... & x_{n-2} & x_{n-1}\\ x_{n-1} & x_0 & ... & x_{n-3} & x_{n-2}\\ ... & ... & ... & ... & ...\\ x_2 & x_3 &... & x_0 & x_1\\ x_1 & x_2 & ... & x_{n-1} & x_0\end{pmatrix}

Theorem 1. \det(X)=\prod_{k=0}^{n-1}\left ( \sum_{j=0}^{n-1}x_j \epsilon_k^j\right ), where \epsilon is a primitive n-th root of unity.

We multiply the  j-columm with \epsilon^{j-1}, \ j=2,3,...,n, and add it onto the first columm, claim that \epsilon^n=1, we have:

 

The j-element of the first columm is a product of x_0+x_1\epsilon+...+x_{n-1}\epsilon^{n-1} with \epsilon^{j-1}, \ j=1,2,...,n. We give \det(X) as a polynomial with n variable x_1,x_2,...,x_n on \mathbb{C}[x], hence \det(X) is devided  by x_0+x_1\epsilon+...+x_{n-1}\epsilon^{n-1}. Claim that \det(X) is a n-degree polynomial and the coefficient of x_0x_1...x_{n-1} is 1.

Thus \det(X)=\prod_{k=0}^{n-1}\left ( \sum_{j=0}^{n-1} \epsilon_k^jx_j \right ) \bigstar

For k=0,1,2,...,n-1, we denote  e_k=\frac{1}{\sqrt{n}}(1,\epsilon_k,...,\epsilon_k^{n-1})^T and
\lambda_k= x_0+x_1\epsilon_k+...+x_{n-1}\epsilon_k^{n-1}

We can easily calculate and receive that Xe_k=\lambda_k e_k and since \{e_0,e_1,...,e_{n-1}\} is a linearly independent system, we conclude that \lambda_0,\lambda_1,...,\lambda_{n-1} are eigenvalues of circulant matrix X

Some results:

i.  trace(X)=\sum_{k=0}^{n-1}\lambda_k=nx_0

ii. With non-singular matrix

 P=\frac{1}{\sqrt{n}} \begin{pmatrix}1 & 1 & ... & 1 & 1\\ 1 & \epsilon & ... & \epsilon^{n-2} & \epsilon^{n-1}\\ ... & ... & ... & ... & ...\\ 1 & \epsilon^{n-2} & ....& \epsilon^{(n-2)^2}& \epsilon^{(n-1)(n-2)}\\ 1 & \epsilon^{n-1} & ... & \epsilon^{(n-2)(n-1)} & \epsilon^{(n-1)^2} \end{pmatrix}

then P^{-1}XP=diag(\lambda_0,\lambda_1,...,\lambda_{n-1})

iii  X=\sum_{k=0}^{n-1}x_kW^k where W=circ(0,1,0,...,0)

(To be continued)

Chéo hóa ma trận bằng phương pháp Jacobi

July 15, 2009 4 comments

Có thể nói đây là phương pháp đơn giản nhất đối với bài toán chéo hóa các ma trận đối xứng.

Giả sử ma trận A\in M_n(\mathbb{R}) đối xứng. Ta xây dựng dãy ma trận trực giao (R_k)_{k\ge1} và dãy ma trận (D_k)_{k\ge 0} như sau

 

D_0=A, \ D_k=R_k^T D_{k-1}R_k, \ \ k=1,2,...

 

sao cho \displaystyle\lim_{k\to\infty} D_k = diag(\lambda_1,\lambda_2,...,\lambda_n) là dạng chéo hóa của A.

 

Thiết lập một dãy như vậy được gọi là quá trình lặp Jacobi

 

Tại bước thứ k của quá trình này D_{k}=R_{k}^T D_{k-1}R_k chúng ta sẽ làm cho phần tử d^{(k)}_{pq}=d^{(k)}_{qp} nằm ngoài đường chéo chính nhận giá trị 0 bằng cách đặt

 

R_k=\begin{pmatrix}1 & 0 & ... & 0 & ... & 0 &... & 0 & 0\\ 0 & 1 & ... & 0 & ... & 0 &... & 0 & 0\\ ...& ... & ... & ... & ... & ... &... & ... & ...\\ 0 & 0 & ... & c & ... & s &... & 0 & 0\\ ...& ... & ... & ... & ... & ... &... & ... & ...\\ 0 & 0 & ... & -s & ... & c &... & 0 & 0\\ ...& ... & ... & ... & ... & ... &... & ... & ...\\ 0 & 0 & ... & 0 & ... & 0 &... & 1 & 0\\ 0 & 0 & ... & 0 & ... & 0 &... & 0 & 1\end{pmatrix}

 

trong đó c=\cos\varphi, s=\sin\varphi

 

Tương ứng với phép biến đổi

d^{(k)}_{jp}=cd^{(k-1)}_{jp}-sd^{(k-1)}_{jq}, \ j\neq p, \ j\neq q

d^{(k)}_{jq}=s d^{(k-1)}+c d^{(k-1)}_{jq}j\neq p, \ j\neq q

d^{(k)}_{pp}=c^2d^{(k-1)}_{pp}+s^2 d^{(k-1)}_{qq}-2csd^{(k-1)}_{pq}

 

d^{(k)}_{qq}=c^2d^{(k-1)}_{pp}+s^2 d^{(k-1)}_{qq}+2csd^{(k-1)}_{pq}

 

d^{(k)}_{pq}=(c^2-s^2)d^{(k-1)}_{pq}+cs\left( d^{(k-1)}_{pp}-d^{(k-1)}_{qq} \right)

 

Giả sử d^{(k-1)}_{pq}\neq 0, chúng ta muốn rằng d^{(k)}_{pq}=0 nên từ phương trình cuối cùng ta có

 

\theta=\cot2\varphi=\frac{c^2-s^2}{cs}=\frac{ d^{(k-1)}_{pp}-d^{(k-1)}_{qq}}{d^{(k-1)}_{pq}}

 

Ta đặt \displaystyle t=\tan\varphi=\frac{s}{c} suy ra \displaystyle\theta=\frac{1-s^2/c^2}{2s/c}=\frac{1-t^2}{2t}, dẫn đến phương trình bậc 2

 

t^2+2\theta t-1=0

 

với nghiệm \displaystyle t=\frac{sign(\theta)}{|\theta|+\sqrt{\theta^2+1}}. Từ đây ta tính được

 

c=\displaystyle\frac{1}{\sqrt{1+t^2}}, \ \ s=ct

 

Chúng ta xét các tổng các phần tử nằm ngoài đường chéo chính

 

S_k= \sum_{i\neq j, \ i,j=1...n} |d^{(k)}_{ij}|^2

 

Khi đó theo hệ phương trình đã xét ta có S_k=S_{k-1}-2|d^{(k-1)}_{ij}|^2

 

Như vậy dãy (S_k)_{k\ge 1} đơn điệu giảm và bị chặn dưới bởi 0 nên nó hội tụ.

 

Với vị trí (p,q) cần đưa về d^{(k)}_{pq}=0 trong ma trận D_k ta chọn tại vị trí của phần tử \displaystyle\max_{p<q}\{ |d^{(k-1)}_{pq}|\} trong ma trận D_{k-1}.

 

Với cách chọn như vậy thì (S_k)_{k\ge 1} hội tụ về 0 và hệ quả là (D_k)_{k\ge 0} hội tụ về ma trận đường chéo K. Ta biết rằng đa thức đặc trưng ma trận luôn bất biến với phép đồng dạng nên K chính là dạng chéo hóa của A.

 

Quá trình này được cài đặt với Mathematica như sau

 

Jacobi1 

 Jacobi2

Ví dụ.  

A=\begin{pmatrix} 8 & -1 & 3 & -1 \\ -1 & 6 & 2 & 0 \\ 3 & 2 & 9 & 1 \\ -1 & 0 & 1 & 7 \end{pmatrix}

 

Ta làm như sau:

 

{K, V} = JacobiCyclic[A, 10^-11, 50];

Print[” K=”, MatrixForm[Chop[K]]];

Print[” V=”, MatrixForm[Chop[V]]];

 

Khi đó kết quả thu được là dạng chéo hóa

 

K=\begin{pmatrix} 6.59234 & 0 & 0 & 0 \\ 0 & 3.2957 & 0 & 0 \\ 0 & 0 & 11.7043 & 0 \\ 0 & 0 & 0 & 8.40766 \end{pmatrix}

 

và ma trận trực giao

 

V=\begin{pmatrix} 0.230097 & 0.528779 & 0.582298 & -0.573042 \\ 0.628975 & 0.591967 & 0.175776 & 0.472301 \\ -0.0712347 & -0.536039 & 0.792487 & 0.28205 \\ 0.739169 & 0.287455 & 0.0446803 & 0.607455\end{pmatrix}

 

thỏa mãn A=V^T K V.

 

Categories: Matrix Theory Tags:

Bất đẳng thức liên quan đến giá trị kì dị của ma trận

June 4, 2009 Leave a comment

Đối với hệ vector ta ký hiệu

Mệnh đề 1: Nếu là các giá trị riêng của  thế thì với hệ vector thì

Đặt \{e_1,e_2,...,e_n\} là cơ sở trực chuẩn cũng đồng thời là các vector riêng của toán tử A.

Ta có (Ax_i,x_j)=\sum_{k=1}^n\alpha_k(x_i,e_k)\overline{(x_j,e_k)}=\sum_{k=1}^n\alpha_k(x_i,e_k)(e_k,x_j)

Khai triển theo công thức Binet-Cauchy ta nhận được

\Gamma(Ax_i,x_j)=\sum_{1\le k_1<...<k_m\le n}\Gamma(x_i,\alpha_k e_k)\Gamma(e_k,x_j)

Áp dụng bất đẳng thức Cauchy-Schwarz ta có

(\Gamma(Ax_i,x_j))^2\le (\sum_{1\le k_1<...<k_m\le n}(\Gamma(x_i,\alpha_k e_k))^2)(\sum_{1\le k_1<...<k_m\le n}(\Gamma(e_k,x_j))^2)

\le \alpha_1^2\alpha_2^2...\alpha_m^2 (\Gamma(x_i,x_j))^2

Mệnh đề 2: Giả sử là các giá trị riêng của (singular values). Thế thì với bất kì hệ vector () thì

Điều này hiển nhiên là hệ quả của mệnh đề 1.

Mệnh đề 3: Cho AB – toán tử tuyến tính trong \mathbb{R}, , là giá trị riêng của toán tử tương ứng, được đánh số thứ tự giảm dần theo giá trị. Chứng minh với ta có

Giả sử là cơ sở trực chuẩn hợp từ cơ sở trực chuẩn cũng đồng thời là các vector riêng của

(Áp dụng MĐ2 hai lần)

Tích Kronecker

June 2, 2009 Leave a comment

là các không gian tuyến tính với số chiều tương ứng là , các cơ sở tương ứng là

Xét các ánh xạ tuyến tính

Xét ánh xạ tuyến tính xác định bởi

sao cho trong đó

Dễ thấy với

được gọi là tích tensor của các ánh xạ tuyến tính

Ta xét trường hợp tích tensor của hai ánh xạ tuyến tính


Với tương ứng là cơ sở của

với
với

Khi đó

với

Xét các ma trận tương ứng của . Ma trận tương ứng của gọi là tích Kronecker của A và B, ký hiệu .

Như vậy có dạng khối hay

Ta có các kết quả sau:

Với A là ma trận cấp , B là ma trận cấp

1.
2. , với A, B, C, D phù hợp nhau về số chiều trong tích ma trận thông thường
3.
4. A, B trực giao hoặc lũy linh thì tích Kronecker cũng trực giao hoặc lũy linh
5. , với A, B khả nghịch
6.

Tích Tensor các không gian Tuyến tính

July 19, 2008 Leave a comment

Bài này nhằm mục đích giúp các bạn tiếp cận với Đại số Đa tuyến Tính một các trực quan trên cơ sở đã hiểu biết Đại số Tuyến tính, tránh bắt gặp ban đầu các lý thuyết quá trừu tượng… Hi vọng bạn đọc cho ý kiến đóng góp.

V_1, V_2,...,V_k là các không gian tuyến tính với số chiều tương ứng là n_1,...,n_k, các cơ sở tương ứng là
\{e_{11},e_{12},...,e_{1n_1}\}, \{e_{21},e_{22},...,e_{2n_2}\},...,\{e_{k1},e_{k2},...,e_{kn_k}\},
V là một không gian tuyến tính

Một ánh xạ f từ V_1\times V_2\times ...\times V_k\rightarrow V,

được gọi là ánh xạ k-tuyến tính nếu là tuyến tính tại mỗi thành phần u_i của (u_1,u_2,...,u_k)\in V_1\times V_2\times ...\times V_k (khi cố định các thành phần còn lại). Ta có:

\displaystyle f(\sum_{1\le i_1\le n_1} x_{1i_1}e_{1i_k},....,\sum_{1\le i_k\le n_k} x_{ki_k}e_{ki_k})
=\displaystyle\sum_{1\le i_j\le n_j, 1\le j\le k} x_{1i_1}x_{2i_2}...x_{ki_k}f(e_{1i_1},e_{2i_2},...,e_{ki_k})

Như vậy f có thể xác định qua n_1.n_2...n_k giá trị của f(e_{1i_1},e_{2i_2}...,e_{ki_k}) với 1\le i_j\le n_j, j=1,2,...,k

Khi V có số chiều là 1, thì f gọi là dạng k-tuyến tính (hình dung lại dạng song tuyến tính quen thuộc)

Xét không gian n_1.n_2...n_k chiều T với vector cơ sở có dạng \epsilon_{i_1,i_2,..,i_k} với 1\le i_j \le n_j, j=1,2,...,k.

Ta xây dựng ánh xạ k-tuyến tính  \widehat{f}: V_1\times V_2\times ...\times V_k\rightarrow T sao cho

\displaystyle f(\sum_{1\le i_1\le n_1} x_{1i_1}e_{1i_k},....,\sum_{1\le i_k\le n_k} x_{ki_k}e_{ki_k})
\displaystyle=\sum_{1\le i_j\le n_j, 1\le j\le k} x_{1i_1}x_{2i_2}...x_{ki_k}\epsilon_{i_1,i_2,..,i_k}

Khi đó có ánh xạ tuyến tính \overline{f}:T\rightarrow V sao cho
\overline{f}(\epsilon_{i_1,i_2,..,i_k})=f(e_{1i_1},e_{2i_2},...e_{ki_k})

Rõ ràng \overline{f}\widehat{f}=f

\overline{f} xác định thỏa mãn đẳng thức trên là duy nhất theo f

Cặp (T, \widehat{f}) xây dựng như vậy gọi là tích Tensor của V_1, V_2,...,V_k, kí hiệu T=V_1\otimes V_2\otimes...\otimes V_k

Người ta cũng kí hiệu \widehat{f}(u_1,u_2,...,u_k)= u_1\otimes u_2\otimes...\otimes u_k
với (u_1,...,u_k)\in V_1\times V_2\times ...\times V_k

Và do đó:

\epsilon_{i_1,i_2,..,i_k}= \widehat{f}(e_{1i_1},e_{2i_2},...,e_{ki_k})= e_{1i_1}\otimes e_{2i_2}\otimes...\otimes e_{ki_k}