Archive

Archive for the ‘Matrix Theory’ Category

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

Advertisements

Đồ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.

Đồng nhất thức Muir

June 2, 2009 Leave a comment

Đồng nhất thức Muir:

ở đây là kí hiệu tích Hadamard của , tức là ma trận mà ở vị trí (i,j) có phần tử là
là ma trận mà dòng thứ i của nó là dòng thứ của ma trận

Chứng minh

Bên vế trái ứng cặp phép thế có các số hạng dạng

Còn bên vế phải ứng với một cặp phép thế thì có các số hạng dạng



Như vậy là cả hai vế đều có tất cả là số hạng, hơn nữa so sánh mỗi số hạng ở hai vế thì là một tương ứng 1-1

Categories: Matrix Theory Tags: