精华内容
下载资源
问答
  • 循环矩阵傅里叶对角化

    万次阅读 多人点赞 2016-03-15 14:10:30
    “任意循环矩阵可以被傅里叶变换矩阵对角化”这个概念常常出现在论文中,本文其做简单解释。

    All circulant matrices are made diagonal by the Discrete Fourier Transform (DFT), regardless of the generating vector x.
    任意循环矩阵可以被傅里叶变换矩阵对角化。

    文献中,一般用如下方式表达这一概念:
    X = C ( x ) = F ⋅ d i a g ( x ^ ) ⋅ F H X=C(x)=F \cdot diag(\hat{x}) \cdot F^H X=C(x)=Fdiag(x^)FH

    其中 X X X是循环矩阵, x ^ \hat{x} x^是原向量 x x x的傅里叶变换, F F F是傅里叶变换矩阵,上标H表示共轭转置: X H = ( X ∗ ) T X^H=(X^{*})^T XH=(X)T
    换句话说, X X X相似于对角阵, X X X的特征值是 x ^ \hat x x^的元素。

    另一方面,如果一个矩阵能够表示成两个傅里叶矩阵夹一个对角阵的乘积形式,则它是一个循环矩阵。其生成向量是对角元素的傅里叶逆变换:

    F ⋅ d i a g ( y ) ⋅ F H = C ( F − 1 ( y ) ) F \cdot diag(y) \cdot F^H = C(\mathcal{F}^{-1}(y)) Fdiag(y)FH=C(F1(y))
    这个公式初看疑问很多,以下一一讨论。

    X X X是什么?

    X X X是由原向量 x x x生成的循环矩阵。以矩阵尺寸 K = 4 K=4 K=4为例。

    X = C ( x ) = [ x 1 x 2 x 3 x 4 x 4 x 1 x 2 x 3 x 3 x 4 x 1 x 2 x 2 x 3 x 4 x 1 ] X=C(x)=\begin{bmatrix} x_1 & x_2 & x_3 & x_4 \\ x_4 & x_1 & x_2 & x_3 \\ x_3 & x_4 & x_1 & x_2 \\ x_2 & x_3 & x_4 & x_1 \\ \end{bmatrix} X=C(x)=x1x4x3x2x2x1x4x3x3x2x1x4x4x3x2x1

    F F F 是什么?

    F F F是离散傅里叶矩阵(DFT matrix),可以用一个复数 ω = e − 2 π i / K \omega = e^{-2\pi i/K} ω=e2πi/K表示,其中 K K K为方阵 F F F的尺寸。以 K = 4 K=4 K=4为例。

    F = 1 K [ 1 1 1 1 1 ω ω 2 ω 3 1 ω 2 ω 4 ω 6 1 ω 3 ω 6 ω 9 ] F=\frac{1}{\sqrt{K}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^2 & \omega^3 \\ 1 & \omega^2 & \omega ^4 & \omega^6 \\ 1 & \omega^3 & \omega^6 & \omega^9 \end{bmatrix} F=K 111111ωω2ω31ω2ω4ω61ω3ω6ω9

    ω \omega ω想象成一个角度为 2 π / K 2\pi/K 2π/K的向量,这个矩阵的每一行是这个向量在不断旋转。从上到下,旋转速度越来越快。

    之所以称为DFT matrix,是因为一个信号的DFT变换可以用此矩阵的乘积获得:

    x ^ = D F T ( x ) = K ⋅ F ⋅ x \hat{x}=DFT(x)=\sqrt{K}\cdot F \cdot x x^=DFT(x)=K Fx

    反傅里叶变换也可以通过类似手段得到:

    x = 1 K F − 1 x ^ x=\frac{1}{\sqrt{K}}F^{-1}\hat{x} x=K 1F1x^

    傅里叶矩阵有许多性质:

    • 是对称矩阵,观察 ω \omega ω的规律即可知;
    • 满足 F H F = F F H = I F^HF=FF^H=I FHF=FFH=I,也就是说它是个酉矩阵(unitary)。可以通过将 F H F^{H} FH展开成 ω H \omega^{H} ωH验证。

    注意: F F F是常数,可以提前计算好,和要处理的 x x x无关。

    对角化怎么理解?

    把原公式两边乘以逆矩阵:

    F − 1 ⋅ X ⋅ ( F H ) − 1 = d i a g ( x ^ ) F^{-1} \cdot X \cdot (F^H)^{-1}=diag(\hat{x}) F1X(FH)1=diag(x^)
    利用前述酉矩阵性质:
    左 边 = F H X F = d i a g ( x ^ ) 左边=F^{H}XF=diag(\hat{x}) =FHXF=diag(x^)

    也就是说,矩阵 X X X通过相似变换 F F F变成对角阵 d i a g ( x ^ ) diag(\hat{x}) diag(x^),即对循环矩阵 X X X进行对角化。
    另外, F H X F F^HXF FHXF是矩阵 X X X的2D DFT变换。即傅里叶变换可以把循环矩阵对角化。

    怎么证明?

    可以用构造特征值和特征向量的方法证明(参看这篇论文1的3.1节),此处简单描述。
    考察待证明等式的第k列:
    X ⋅ f k = x ^ k ⋅ f k X\cdot f_k=\hat x_k\cdot f_k Xfk=x^kfk

    其中 f k f_k fk表示DFT矩阵的第k列, x ^ k \hat x_k x^k表示傅里叶变换的第k个元素。等价于求证: f k f_k fk x ^ k \hat x_k x^k X X X的一对特征向量和特征值。

    左边向量的第i个元素为: l e f t i = [ x i , f k ] left_i = \left[ x^i, f_k \right] lefti=[xi,fk] x i x_i xi表示把生成向量 x x x向右移动i位, [ ] [] []表示内积。
    内积只和两个向量的相对位移有关,所以可以把 f k f_k fk向左移动i位: l e f t i = [ x , f k − i ] left_i=\left[ x, f_k^{-i}\right] lefti=[x,fki]
    DFT矩阵列的移位可以通过数乘 ω \omega ω的幂实现: f k i = f 0 ⋅ ω i k f_k^i=f_0\cdot \omega^{ik} fki=f0ωik

    举例: K = 3 K=3 K=3
    F = 1 K [ 1 1 1 1 ω ω 2 1 ω 2 ω 4 ] F=\frac{1}{\sqrt{K}} \begin{bmatrix} 1 & 1 & 1\\ 1 & \omega & \omega^2 \\ 1 & \omega^2 & \omega ^4 \end{bmatrix} F=K 11111ωω21ω2ω4

    利用 ω N = 1 \omega^N=1 ωN=1.
    f 1 ⋅ ω = [ 1 , ω , ω 2 ] ⋅ ω = [ ω , ω 2 , ω 3 ] = [ ω , ω 2 , 1 ] = f 1 − 1 f_1\cdot \omega =[1,\omega,\omega^2]\cdot \omega = [\omega, \omega^2,\omega^3] = [\omega, \omega^2, 1]=f_1^{-1} f1ω=[1,ω,ω2]ω=[ω,ω2,ω3]=[ω,ω2,1]=f11

    f 1 ⋅ ω 2 = [ 1 , ω , ω 2 ] ⋅ ω 2 = [ ω 2 , ω 3 , ω 4 ] = [ ω 2 , 1 , ω ] = f 1 − 2 f_1\cdot \omega^2 =[1,\omega,\omega^2]\cdot \omega^2 = [\omega^2, \omega^3,\omega^4] = [\omega^2, 1, \omega]=f_1^{-2} f1ω2=[1,ω,ω2]ω2=[ω2,ω3,ω4]=[ω2,1,ω]=f12

    于是有:
    l e f t i = [ x , f k ⋅ ω i k ] = [ x , f k ] ⋅ ω i k left_i= \left [x, f_k \cdot \omega^{ik}\right ]=\left [x, f_k\right ] \cdot \omega^{ik} lefti=[x,fkωik]=[x,fk]ωik

    右边的$\hat x = F\cdot x , 考 虑 到 ,考虑到 F 的 第 k 行 和 第 k 列 相 同 , 的第k行和第k列相同, kk\hat x_k=[f_k,x] 。 另 外 。另外 f_k 的 第 i 个 元 素 为 的第i个元素为 i\omega^{ik}$:
    r i g h t i = x ^ k ⋅ f k i = [ f k ∗ , x ] ⋅ ω k i right_i = \hat x_k\cdot f_{ki}=[f_k^*,x]\cdot \omega^{ki} righti=x^kfki=[fk,x]ωki

    对任意k列的第i个元素有: l e f t i = r i g h t i left_i=right_i lefti=righti

    更多性质

    利用对角化,能推导出循环矩阵的许多性质。

    转置

    循环矩阵的转置也是一个循环矩阵(可以查看循环矩阵各元素排列证明),其特征值和原特征值共轭。
    X T = F ⋅ d i a g ( ( x ^ ) ∗ ) ⋅ F H X^T=F \cdot diag((\hat{x})^*) \cdot F^H XT=Fdiag((x^))FH
    可以通过如下方式证明:
    X T = ( F H ) T ⋅ d i a g ( x ^ ) F T X^T=(F^H)^T\cdot diag(\hat x) F^T XT=(FH)Tdiag(x^)FT
    由于 F F F是对称酉矩阵,且已知 X X X是实矩阵:
    X T = F ∗ ⋅ d i a g ( x ^ ) F = ( F ∗ ⋅ d i a g ( x ^ ) F ) ∗ = F ⋅ d i a g ( ( x ^ ) ∗ ) ⋅ F H X^T=F^*\cdot diag(\hat x) F=\left( F^*\cdot diag(\hat x) F\right)^*=F\cdot diag((\hat x)^*) \cdot F^H XT=Fdiag(x^)F=(Fdiag(x^)F)=Fdiag((x^))FH

    如果原生成向量 x x x是对称向量(例如[1,2,3,4,3,2]),则其傅里叶变换为实数,则:
    X T = C ( F − 1 ( x ^ ) ∗ ) = C ( x ) X^T=C\left( \mathcal F^{-1}(\hat x)^* \right)=C(x) XT=C(F1(x^))=C(x)

    卷积

    循环矩阵乘向量等价于生成向量的逆序和该向量卷积,可进一步转化为福利也变化相乘。
    注意卷积本身即包含逆序操作,另外利用了信号与系统中经典的“时域卷积,频域相乘”。

    F ( X y ) = F ( C ( x ) y ) = F ( x ˉ ∗ y ) = F ∗ ( x ) ⊙ F ( y ) \mathcal{F}(Xy) = \mathcal{F}(C(x)y)=\mathcal{F}(\bar x*y)=\mathcal{F}^*(x)\odot \mathcal{F}(y) F(Xy)=F(C(x)y)=F(xˉy)=F(x)F(y)
    其中 x ˉ \bar x xˉ表示把 x x x的元素倒序排列。星号表示共轭。

    相乘

    C , B C,B C,B为循环矩阵,其乘积的特征值等于特征值的乘积:

    A B = F ⋅ d i a g ( a ^ ) ⋅ F H ⋅ F ⋅ d i a g ( b ^ ) ⋅ F H AB = F\cdot diag(\hat a) \cdot F^H \cdot F \cdot diag(\hat b) \cdot F^H AB=Fdiag(a^)FHFdiag(b^)FH

    = F ⋅ d i a g ( a ^ ) ⋅ d i a g ( b ^ ) ⋅ F H = F ⋅ d i a g ( a ^ ⊙ b ^ ) ⋅ F H = F\cdot diag(\hat a) \cdot diag(\hat b) \cdot F^H=F\cdot diag(\hat a \odot \hat b) \cdot F^H =Fdiag(a^)diag(b^)FH=Fdiag(a^b^)FH

    = C ( F − 1 ( a ^ ⊙ b ^ ) ) =C\left( \mathcal F^{-1}(\hat a \odot \hat b)\right) =C(F1(a^b^))
    乘积也是循环矩阵,其生成向量是原生成向量对位相乘的傅里叶逆变换。

    相加

    和的特征值等于特征值的和:
    A + B = F ⋅ d i a g ( a ^ ) ⋅ F H + F ⋅ d i a g ( b ^ ) ⋅ F H = F ⋅ d i a g ( a ^ + b ^ ) ⋅ F H A+B = F\cdot diag(\hat a) \cdot F^H + F \cdot diag(\hat b) \cdot F^H=F\cdot diag(\hat a +\hat b) \cdot F^H A+B=Fdiag(a^)FH+Fdiag(b^)FH=Fdiag(a^+b^)FH

    = C ( F − 1 ( a ^ + b ^ ) ) = C ( F − 1 ( a ^ ) + F − 1 ( b ^ ) ) = C ( a + b ) =C\left( \mathcal F^{-1} (\hat a +\hat b)\right)=C\left( \mathcal F^{-1} (\hat a )+F^{-1} (\hat b )\right)=C\left( a+b\right) =C(F1(a^+b^))=C(F1(a^)+F1(b^))=C(a+b)
    和也是循环矩阵,其生成向量是原生成向量的和。

    求逆

    循环矩阵的逆,等价于将其特征值求逆。
    X − 1 = F ⋅ d i a g ( x ^ ) − 1 F H = C ( F − 1 ( d i a g ( x ^ ) − 1 ) ) X^{-1}=F\cdot diag(\hat{x})^{-1}F^H=C\left( \mathcal F^{-1}(diag(\hat{x})^{-1}) \right) X1=Fdiag(x^)1FH=C(F1(diag(x^)1))
    对角阵求逆等价于对角元素求逆。以下证明:
    F ⋅ d i a g ( x ^ ) − 1 ⋅ F H ⋅ F ⋅ d i a g ( x ^ ) ⋅ F H F\cdot diag(\hat{x})^{-1}\cdot F^H \cdot F\cdot diag(\hat{x}) \cdot F^H Fdiag(x^)1FHFdiag(x^)FH

    = F ⋅ d i a g ( x ^ ) − 1 ⋅ d i a g ( x ^ ) ⋅ F H = F ⋅ F H = I =F\cdot diag(\hat{x})^{-1}\cdot diag(\hat{x}) \cdot F^H=F\cdot F^H=I =Fdiag(x^)1diag(x^)FH=FFH=I

    逆也是循环矩阵

    有什么用?

    该性质可以将循环矩阵的许多运算转换成更简单的运算。例如:

    X H X = F ⋅ d i a g ( x ^ ⊙ x ^ ∗ ) ⋅ F H = C ( F − 1 ( x ^ ⊙ x ^ ∗ ) ) X^HX=F \cdot diag(\hat{x} \odot \hat{x}^*)\cdot F^H=C\left( \mathcal F^{-1}(\hat{x} \odot \hat{x}^*) \right) XHX=Fdiag(x^x^)FH=C(F1(x^x^))

    原始计算量:两个方阵相乘( O ( K 3 ) O(K^3) O(K3)
    转化后的计算量:反向傅里叶( K log ⁡ K K\log K KlogK)+向量点乘( K K K)。

    CV的许多算法中,都利用了这些性质提高运算速度,例如2015年TPAMI的这篇高速跟踪KCF方法2

    二维情况

    以上探讨的都是原始信号为一维的情况。以下证明二维情况下的 F H X F = d i a g ( x ^ ) F^HXF=diag(\hat x) FHXF=diag(x^),推导方法和一维类似。

    x x x是二维生成矩阵,尺寸 N × N N\times N N×N
    X X X是一个 N 2 × N 2 N^2\times N^2 N2×N2的分块循环矩阵,其uv块记为 x u v x^{uv} xuv,表示 x x x下移u行,右移v列。
    F F F N 2 × N 2 N^2\times N^2 N2×N2的二维DFT矩阵,其第uv块记为 f u v = { ω u i + v j } i j f_{uv}=\left\{ \omega^{ui+vj} \right\} _{ij} fuv={ωui+vj}ij

    举例:N=3 f 01 = [ 1 ω ω 2 1 ω ω 2 1 ω ω 2 ] , f 11 = [ 1 ω ω 2 ω ω 2 ω 3 ω 2 ω 3 ω 4 ] f_{01}=\begin{bmatrix} 1 & \omega & \omega^2 \\ 1 & \omega & \omega^2 \\ 1 & \omega & \omega^2\end{bmatrix}, f_{11}=\begin{bmatrix} 1 & \omega & \omega^2 \\ \omega & \omega^2 & \omega^3 \\ \omega^2 & \omega^3 & \omega^4\end{bmatrix}\\ f01=111ωωωω2ω2ω2,f11=1ωω2ωω2ω3ω2ω3ω4

    需要验证的共有 N × N N\times N N×N个等式,其中第 u v uv uv个为:
    [ X , f u v ] = x ^ u v ⋅ f u v [X, f_{uv}]=\hat x_{uv}\cdot f_{uv} [X,fuv]=x^uvfuv
    其中 [ X , f u v ] [X, f_{uv}] [X,fuv]表示把 x u v x^{uv} xuv分别和 f u v f_{uv} fuv做点乘,结果矩阵元素求和。
    这个等式的第ij元素为:
    [ x i j , f u v ] = x ^ u v ⋅ ω u i + v j [x^{ij},f_{uv}]=\hat x_{uv} \cdot \omega^{ui+vj} [xij,fuv]=x^uvωui+vj

    再次利用两个性质:1) 点乘只和两个矩阵相对位移有关,2) f u v f_{uv} fuv的位移可以用乘 ω \omega ω幂实现:
    l e f t i j = [ x , f u v − i − j ] = [ x , f u v ] ⋅ ω u i + v j = x ^ u v ⋅ ω u i + v j = r i g h t i j left_{ij}=[x,f_{uv}^{-i-j}]=[x,f_{uv}]\cdot \omega^{ui+vj}=\hat x_{uv} \cdot \omega^{ui+vj}=right_{ij} leftij=[x,fuvij]=[x,fuv]ωui+vj=x^uvωui+vj=rightij

    代码

    以下matlab代码验证上述性质。需要注意的是,matlab中的dftmatx函数给出的结果和本文定义略有不同,需做一简单转换。另外,matlab中的撇号表示共轭转置,transpose为转置函数,conj为共轭函数。

    clear;clc;close all;
    
    % 1. diagnolize 
    K = 5;      % dimension of problem
    
    x_base = rand(1,K);     % generator vector
    X = zeros(K,K);         % circulant matrix
    for k=1:K
        X(k,:) = circshift(x_base, [0 k-1]);
    end
    
    x_hat = fft(x_base);    % DFT
    
    F = transpose(dftmtx(K))/sqrt(K);       % the " ' " in matlab is transpose + conjugation
    
    X2 = F*diag(x_hat)*F';
    
    display(X);
    display(real(X2));
    
    % 2. fast compute correlation
    C = X'*X;
    C2 = (x_hat.*conj(x_hat))*conj(F)/sqrt(K);
    
    display(C);
    display(C2);
    

    1. Gray, Robert M. Toeplitz and circulant matrices: A review. now publishers inc, 2006. ↩︎

    2. Henriques, João F., et al. “High-speed tracking with kernelized correlation filters.” Pattern Analysis and Machine Intelligence, IEEE Transactions on 37.3 (2015): 583-596. ↩︎

    展开全文
  • 实对称矩阵一定可以对角化

    万次阅读 2020-06-28 11:11:44
    实对称矩阵一定可以对角化. 最近看共轭梯度下降的时候看到有人的推导里面用到了这个命题. 虽然以前学过, 但是学得很渣, 所以没有自己想过这个命题怎么样成立的. 现在将这些证明过程梳理一下. 实对称矩阵含有n个实根 ...

    UTF8gbsn

    实对称矩阵一定可以对角化.
    最近看共轭梯度下降的时候看到有人的推导里面用到了这个命题. 虽然以前学过,
    但是学得很渣, 所以没有自己想过这个命题怎么样成立的.
    现在将这些证明过程梳理一下.

    实对称矩阵含有n个实根

    首先我们来证明一个命题, 实对称矩阵含有n个实根,
    注意,n个实根并不一定都是不同的, 可能含有重根.
    比如 ( r − 1 ) 2 = 0 (r-1)^2=0 (r1)2=0就含有两个重根 r = 1 r=1 r=1.在计算根数目的时候这个方程的解算两个.

    • 首先, 任意的矩阵 A \mathbf{A} A,它的特征多项式
      ∣ A − λ I ∣ = 0 |\mathbf{A}-\lambda\mathbf{I}|=0 AλI=0
      是一个 n n n次多项式(这是很显然的).
      由于 n n n次多项式必定有 n n n个根(在复数域上). 这个命题暂不证明,
      直接使用. 我写过另外一篇文章简要的证明了一下这个定理.

    • 有了上一步的结论,
      我们现在只需要证明每一个根 λ i \lambda_i λi是实根就可以了.
      这个证明过程很简单. 假设 λ i \lambda_i λi是任意根之一,
      并且 α i \mathbf{\alpha}_i αi(当然也是在复数域),
      那么根据特征值和特征向量的定义.我们可以得
      A α i = λ i α i \mathbf{A}\mathbf{\alpha}_i=\lambda_i\mathbf{\alpha}_i Aαi=λiαi 取共轭得
      A α ‾ i = λ ‾ i α ‾ i \mathbf{A}\mathbf{\overline{\alpha}}_i=\overline{\lambda}_i\mathbf{\overline{\alpha}}_i Aαi=λiαi
      再进行转置得, 注意 A T = A A^T=A AT=A, 对称矩阵.
      α ‾ i T A = λ ‾ i α ‾ i T \mathbf{\overline{\alpha}}_i^T\mathbf{A}=\overline{\lambda}_i\mathbf{\overline{\alpha}}_i^T αiTA=λiαiT
      右边乘 α i \mathbf{\alpha}_i αi
      α ‾ i T A α i = λ ‾ i α ‾ i T α i \mathbf{\overline{\alpha}}_i^T\mathbf{A}\mathbf{\alpha}_i=\overline{\lambda}_i\mathbf{\overline{\alpha}}_i^T\mathbf{\alpha}_i αiTAαi=λiαiTαi

      再看 A α i = λ i α i \mathbf{A}\mathbf{\alpha}_i=\lambda_i\mathbf{\alpha}_i Aαi=λiαi,
      对它左边乘 α ‾ i T \overline{\mathbf{\alpha}}_i^{T} αiT可得
      α ‾ i T A α i = λ i α ‾ i T α i \mathbf{\overline{\alpha}}_i^T\mathbf{A}\mathbf{\alpha}_i=\lambda_i\mathbf{\overline{\alpha}}_i^T\mathbf{\alpha}_i αiTAαi=λiαiTαi

    • 上面两个式子相减得
      0 = ( λ ‾ i − λ i ) α ‾ i T α i 0=(\mathbf{\overline{\lambda}_i-\lambda_i})\mathbf{\overline{\alpha}}_i^T\mathbf{\alpha}_i 0=(λiλi)αiTαi
      因为, α ‾ i T α i \mathbf{\overline{\alpha}}_i^T\mathbf{\alpha}_i αiTαi是非0向量.所以我们可得 λ ‾ i − λ i = 0 \overline{\lambda}_i-\lambda_i=0 λiλi=0.
      也就是说 λ i \lambda_i λi是实数.
      又因为 λ i \lambda_i λi是任意的特征值,所以 A \mathbf{A} A,
      的所有特征值都是实数.

    实对称矩阵属于不同特征值的特征向量正交

    接下来我们再来证明一个命题,实对称矩阵属于不同特征值的特征向量正交.我们先假设两个不同的特征值位 λ i , λ j \lambda_i,\lambda_j λi,λj,
    他们对应的特征向量为 α i , α j \mathbf{\alpha}_i, \mathbf{\alpha}_j αi,αj. 假如,
    我们定义 ( α i , α j ) (\mathbf{\alpha}_i, \mathbf{\alpha}_j) (αi,αj)表示点积.
    那么我们可以按照下面的推导.

    λ i ( α i , α j ) = ( λ i α i , α j ) = ( A α i , α j ) = α j T A α i = α i T A α j \lambda_i(\mathbf{\alpha}_i, \mathbf{\alpha}_j)=(\lambda_i\mathbf{\alpha}_i, \mathbf{\alpha}_j)=(\mathbf{A\alpha}_i, \mathbf{\alpha}_j)=\mathbf{\alpha_j^TA\alpha_i}=\mathbf{\alpha_i^TA\alpha_j} λi(αi,αj)=(λiαi,αj)=(Aαi,αj)=αjTAαi=αiTAαj
    λ j ( α i , α j ) = ( α i , λ j α j ) = ( α i , A α j ) = α i T A α j \lambda_j(\mathbf{\alpha}_i, \mathbf{\alpha}_j)=(\mathbf{\alpha}_i, \lambda_j\mathbf{\alpha}_j)=(\mathbf{\alpha}_i, \mathbf{A\alpha}_j)=\mathbf{\alpha_i^TA\alpha_j} λj(αi,αj)=(αi,λjαj)=(αi,Aαj)=αiTAαj

    下相减得 ( λ i − λ j ) ( α i , α j ) = 0 (\lambda_i-\lambda_j)(\mathbf{\alpha}_i, \mathbf{\alpha}_j)=0 (λiλj)(αi,αj)=0,
    又因为 λ i ≠ λ j ⇒ α i T ⋅ α j = 0 \lambda_i\neq \lambda_j \Rightarrow \mathbf{\alpha}_i^T\cdot \mathbf{\alpha}_j=0 λi=λjαiTαj=0,
    也就是正交成立.

    实对称矩阵可对角化

    这里我们使用归纳法来证明.

    • 首先假设 n = 1 n=1 n=1. A = a 11 \mathbf{A}=a_{11} A=a11. 这个不证自明.

    • 假设 n = k − 1 n=k-1 n=k1, 命题撤成立.

    • 现在 n = k n=k n=k, 我们假设其中一个特征值位 λ 1 \lambda_1 λ1,
      那么我可以利用第一个特征值对应的特征向量构造一组 R n R^n Rn的正交基.
      T = ( η 1 , η 2 , ⋯   , η n ) T=(\eta_1, \eta_2,\cdots, \eta_n) T=(η1,η2,,ηn). 那么我们可以得
      T − 1 A T = ( T − 1 λ 1 η 1 , T − 1 A η 2 , ⋯   , T − 1 A η n ) T^{-1}AT=(T^{-1}\lambda_1\eta_1, T^{-1}A\eta_2, \cdots, T^{-1}A\eta_n) T1AT=(T1λ1η1,T1Aη2,,T1Aηn)
      又因为 T − 1 T = I T^{-1}T=I T1T=I, 那么,
      我们可以得 T − 1 η 1 = ε 1 T^{-1}\eta_1=\mathbf{\varepsilon}_1 T1η1=ε1. 那么可得
      T − 1 A T = ( λ 1 α 0 B ) T^{-1}AT=\left( \begin{array}{cc} \lambda_1 & \mathbf{\alpha} \\ \mathbf{0} & \mathbf{B} \end{array} \right) T1AT=(λ10αB)

      由于 A A A, 是一个实对称矩阵,
      那么 T − 1 A T T^{-1}AT T1AT也是一个实对称矩阵.进而 α = 0 \mathbf{\alpha}=\mathbf{0} α=0.
      由此可见 B B B也是一个 ( k − 1 ) × ( k − 1 ) (k-1)\times (k-1) (k1)×(k1)的实对称矩阵. 按照假设,
      它是可以对角化的.现在假设.
      T 2 − 1 B T 2 = d i a g { λ 2 , λ 3 , ⋯   , λ n } T_2^{-1}BT_{2}=diag\{\lambda_2, \lambda_3, \cdots, \lambda_n\} T21BT2=diag{λ2,λ3,,λn}
      并设 T f = T ( 1 0 0 T 2 ) T_f=T\left( \begin{array}{cc} 1 & 0 \\ 0 & T_2 \end{array} \right) Tf=T(100T2) 那么 T f − 1 A T f = ( 1 0 0 T 2 ) − 1 T − 1 A T ( 1 0 0 T 2 ) = ( 1 0 0 T 2 − 1 ) ( λ 1 0 0 B ) ( 1 0 0 T 2 ) T^{-1}_fAT_{f}=\left( \begin{array}{cc} 1 & 0 \\ 0 & T_2 \end{array} \right)^{-1}T^{-1}AT\left( \begin{array}{cc} 1 & 0 \\ 0 & T_2 \end{array} \right)=\left( \begin{array}{cc} 1 & 0 \\ 0 & T_2^{-1} \end{array} \right)\left( \begin{array}{cc} \lambda_1 & 0 \\ 0 & B \end{array} \right)\left( \begin{array}{cc} 1 & 0 \\ 0 & T_2 \end{array} \right) Tf1ATf=(100T2)1T1AT(100T2)=(100T21)(λ100B)(100T2) = ( λ 1 0 0 T 2 − 1 B T 2 ) = d i a g { λ 1 , λ 2 , ⋯   , λ n } =\left( \begin{array}{cc} \lambda_1& 0 \\ 0 & T_2^{-1}BT_{2} \end{array} \right)=diag\{\lambda_1,\lambda_2, \cdots, \lambda_n\} =(λ100T21BT2)=diag{λ1,λ2,,λn}

    至此, 原式得证. 也就是说实对称矩阵一定可以对角化.
    反过来也说明实对称矩阵的特征多项式的代叔重述等于几何重数.

    展开全文
  • 相似矩阵矩阵的相似对角化

    万次阅读 多人点赞 2016-10-19 19:12:47
    特殊的,如果A∼Λ,Λ是矩阵A \sim \Lambda, \Lambda 是矩阵, 则称A可以相似对角化。Λ\Lambda是相似标准形。矩阵可相似对角化的充要条件 n阶矩阵A可对角化 ⟺\Longleftrightarrow A有n个线性无关的特征向

    相似矩阵的定义

    A,B都是n阶矩阵。若存在可逆矩阵P,使得 P1AP=B ,则称A相似于B,记作 AB
    特殊的,如果 AΛ,Λ , 则称A可以相似对角化。 Λ 是相似标准形。

    矩阵可相似对角化的充要条件

    • n阶矩阵A可对角化 A有n个线性无关的特征向量。

      注意这里说的不是A的秩为满,也不是 λEA 矩阵秩满时,可以得到A有n个线性无关的特征向量。而是方程 |λEA|=0 可以取得n个特征值。
      一个特征值下有多少无关的特征向量呢?需要代入方程 (λEA)x=0 计算。

    • 不相等的特征值对应的特征向量一定无关。而相同特征值下的特征向量不一定无关(相同特征值还有重数的概念)。即,若 λ1λ2, 则A的对应于 λ1 λ2 的特征向量线性无关。

      由此引出的推论是:若A有n个互不相同的特征值,那么就可以得出A有n个无关的特征向量。从而得出A可以相似对角化,且主对角线元素是n个特征值。

    如果,A有n个线性无关特征向量只有这一种情况的话,将会无聊得太多了。幸而实际上不是。同样的特征值也有可能得出多个无关向量。

    • λi 是n阶矩阵A的 ri 重特征值,则其对应的线性无关特征向量的个数小于等于 ri 个。

    推论:每一个 ri 重特征值对应的线性无关特征向量的个数等于该特征值的重数时,等价于n阶矩阵A可以相似对角化。

    综合上面可以看到,矩阵相似对角化的核心是可以得到矩阵A有n个线性无关的特征向量。已知A可以求出A的特征值,这些特征值不必各个不同,可以部分相同,相同的个数称之为对应的特征值的重数。再根据这个特征值求得的特征向量个数,二者比较,可以得出是不是有n个线性无关的特征向量。

    也就是说,充要条件的限制很大,或者说可选的范围很小。也因此,必要条件就很多。这也成为了解题的一大依据。

    矩阵相似的必要条件

    A simB=(1)|λEA|=|λEB|,(2)r(A)=r(B),(3)AB,(4)|A|=|B|=ni=1λi,(5)ni=1aii=ni=1bii=ni=1λi

    值得注意的是,当两个矩阵相似时,不要认为主对角线秩积等于特征值之积。。。

    初等行变换后,特征值一般会变化。这也是值得注意的点。

    基本上我们常常研究的秩,行列式,特征值,特征方程都相同,但也只是必要条件。

    展开全文
  • 矩阵可相似对角化的条件

    万次阅读 2020-06-20 16:40:27
    矩阵可以对角化的条件为有n个线性无关的特征向量,具体判断为 1.实对称矩阵必定可以相似对角化 2.如果特征值两两互不相同或,那么也可以立马断定矩阵可以相似对角化 3.如果有k重特征值λ,那么n-r(λE-A)=k,因为...

    矩阵可以对角化的条件为有n个线性无关的特征向量,具体判断为

    1.实对称矩阵必定可以相似对角化

    2.如果特征值两两互不相同或,那么也可以立马断定矩阵可以相似对角化

    3.如果有k重特征值λ,那么n-r(λE-A)=k,因为只有这个等式成立,才能说明特征值取λ时有k个线性无关的解向量,即特征向量

    展开全文
  • Note:PCA主成分分析用到实对称阵的相似对角化。1.角阵概念2.矩阵角阵相似的条件3.一般矩阵的相似对角化4.实对称矩阵的相似对角化5.协方差矩阵的相似对角化(end)...
  • 量子力学中的一项基本假定是代表力学量的算符是Hermite算符,由力学量算符的本征方程解出的全部本征值,就是相应力学量的...本文先从数学上严格证明了Hermite矩阵可以酉相似对角化,然后结合物理实例分析了其物理意义。
  • matlab开发-矩阵的双对角化。代码通过调用Lapack例程计算矩阵的双矩阵分解。
  • 本微信图文从变换的角度解释了相似矩阵对角化
  • 矩阵对角化

    千次阅读 2015-11-02 12:15:57
    矩阵对角化
  • 本文从矩阵为什么要对角化讲到为什么不能对角化,解释不能对角化是什么意思可参看视频,主要思想表述如下: 矩阵相似对角化与不能对角化的解释 矩阵相似对角化的进一步理解,几何加本质 一般矩阵的研究转化...
  • 矩阵对角化,SVD分解

    千次阅读 2019-09-20 12:18:39
    - [矩阵对角化](#矩阵对角化) - [SVD分解](#svd分解) - [参考链接](#参考链接) 矩阵对角化 矩阵的相似 设 A\boldsymbol{A}A、 B\boldsymbol{B}B 为两个nnn阶矩阵,若存在可逆矩阵 P\boldsymbol{P}P,使得...
  • 在次转置矩阵性质的基础上,给出了次转置矩阵矩阵的结论,并根据矩阵对角化理论,给出并证明了次转置矩阵对角化的条件。
  • 矩阵对角化的充要条件及证明

    万次阅读 2018-08-04 22:37:04
    对角化:若方阵A相似于矩阵,即存在可逆矩阵P和矩阵D,有,则称A可对角化。 可对角化的充要条件: n*n阶矩阵A可对角化的充分必要条件是矩阵A有n个线性无关的特征向量。 充分性证明: 设A的n个线性无关的...
  • 矩阵对角化

    千次阅读 2015-03-29 10:16:53
    矩阵对角化 讲解矩阵对角化之前,先了解下相似矩阵。 相似矩阵的定义:A、B是n阶矩阵,若存在可逆矩阵P,使得P-1AP = B,(注意全文中所有的P-1=P的逆矩阵)则定义矩阵B是矩阵A的相似矩阵或称矩阵A与矩阵B...
  • 矩阵对角化的条件

    千次阅读 2020-05-29 21:04:36
    总结:对于任意方阵,如果没有重根,矩阵总是可以对角化。麻烦的是重根问题 如果有重根,那么需要验证所谓几何重数,与代数重数相等。 那么对于有重根,不能对角化矩阵怎么办?这就引入了Jordan标准型的故事。 ...
  • 实对称矩阵的相似对角化

    千次阅读 2020-05-18 10:11:28
    每个元素为实数的对角矩阵称为实对称矩阵,实对称矩阵必定相似于一个对角矩阵对角线以外的元素全为0的矩阵),即存在可逆矩阵P,使得,且存在正交矩阵Q,使得 实对称矩阵化为对角矩阵的步骤: 1.找出全部特征...
  • 实对称矩阵必可正交对角化证明

    万次阅读 2018-08-05 13:36:26
    n阶矩阵A可正交对角化的充分条件是A是实对称矩阵,即若A是实对称矩阵则A必可正交对角化。 首先,有以下定理: 若的特征值为,且,则存在正交矩阵Q,使A相似于如下三角矩阵: 证明如下(数学归纳法): 设n*n阶...
  • 相似矩阵和相似对角化

    千次阅读 2018-05-24 19:34:48
    对称矩阵对角化(方阵) 对称矩阵的一些性质: 1:对称矩阵的特征值为实数 2:设λ1λ1\lambda_1和λ2λ2\lambda_2是对称矩阵AAA的两个特征值,p1p1\mathbf{p}_1,p2p2\mathbf{p}_2是对应的特征向量,若λ1≠λ2...
  • 判断一个矩阵是否可对角化

    万次阅读 2016-12-31 23:13:48
    原文:... 将矩阵A的特征多项式完全分解,求出A的特征值及其重数 若k重特征值有k个线性无关的特征向量,则A可对角化. 否则不能角化. 实对称矩阵总可对角化,且可正交对角化.
  • 线性代数笔记8:矩阵对角化

    万次阅读 多人点赞 2018-04-02 21:33:36
    本文主要讲矩阵对角化的证明及应用。 矩阵对角化条件 定义一:若存在可逆矩阵SSS,使得S−1ASS−1ASS^{-1}AS为矩阵,则称为矩阵AAA是可对角化的(diagonalized)。 设n×nn×nn\times n矩阵有nnn个线性...
  • 实对称矩阵相似对角化Matlab程序,用到的朋友可以下载看看。
  • 矩阵对角化:AS = S(讲AS展开可以推导出这个公式) 上式两边的左边同时乘以S-1,得出S-1AS = 。这就是方阵的对角化公式 上式两边的右边同时乘以S-1,得出A = SS-1,这就是矩阵的句对话分解。   如果A的特征值...
  • 矩阵对角化条件

    千次阅读 2019-08-31 16:21:28
    文章目录 充要条件① 定理2 充要条件② 充要条件③ 充要条件① ...可以用这个条件推不可对角化: A A A 的特征多项式若有一个复根 ∉ K \notin K ∈ / ​ K 有一个特征值的几何重数<代数重数
  • 矩阵对角化的计算

    2018-10-12 21:19:05
    每个方阵对应一个线性变换,矩阵对角化的本质是找线性变化的特征值和特征向量。线性变换可以代表一种操作(如坐标系的转动)或者代表一个力学量(如量子力学中的动量、角动量等),运用非常广泛。
  • 矩阵对角化、SVD分解及应用矩阵对角化、SVD分解及应用矩阵运算的总结矩阵对角化SVD分解张量(tensor)转置(transpose) 矩阵对角化、SVD分解及应用 许多数学对象可以通过将它们分解成多个组成部分或者找到它们的...
  • 矩阵对角化的那些事——blog2

    千次阅读 2021-03-19 09:40:52
    对角化的两个小定理小唠嗑定理1:矩阵AAA可对角化的充要条件是AAA有nnn个线性无关的特征向量小定理1:矩阵AAA可对角化等价于矩阵AAA与一个矩阵相似定理2:任意nnn级实对称矩阵AAA正交相似于一个矩阵小定理:...
  • Toeplitz 矩阵对角化

    千次阅读 2015-08-13 10:17:07
    Toeplitz 矩阵是一种比较特殊的矩阵:其中任何一条对角线的元素取相同的值,

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 100,867
精华内容 40,346
关键字:

任何矩阵都可以对角化