矩陣運算的重要性應該不亞于圖算法。先重溫下矩陣的相關概念和性質，為后續矩陣運算奠定數據理論基礎。

矩陣A：數字的一個矩形陣列，形式化為A=(a_ij)，第i行j列元素為a_ij，如元素為實數的所有元素mXn矩陣組合的元素用R^mXn表示。

矩陣轉置A^T：是矩陣A的行和列互相交換而產生的舉證。

向量（Vector）：是數字的一維向量，列向量看成是nX1的矩陣，轉置成行向量就是1Xn的矩陣。

單位向量e_i：矩陣第一個元素為1而其他元素均為0的常量。

零矩陣：所有元素都是0的矩陣。

對角矩陣：當i≠j時，a_ij=0，所有非對角線上的元素均為0。

nXn單位矩陣I_n：是對角線元素都是1的對角矩陣。

三對角矩陣T：滿足|i-j|>1的元素t_ij=0的矩陣，非零元素僅出現在主對角線上、靠主對角線上面和對角線下面。

上三角矩陣U：滿足i>j的元素U_ij=0的矩陣，對角線下面的所有元素均為0，若對角線元素為1，則是單位上三角矩陣。

下三角矩陣L：滿足i<j的元素L_ij=0的矩陣，對角線上面的所有元素均為0，若對角線元素為1，則是單位下三角矩陣。

置換矩陣P：每一行或列中僅包含一個1，其他元素都為0，可以把一個向量x和一個置換矩陣相乘，結果是向量x中的元素的一種置換。

對稱矩陣A：滿足條件A= A^T。

矩陣加法：C(c_ij)=A(a_ij)+B(b_ij)，c_ij=a_ij+b_ij，都是mXn矩陣。

矩陣乘法：相容（A的列數等于B的行數）的兩個矩陣才可以相乘，C(c_ij)=A(a_ik)+B(b_kj)，矩陣和單位矩陣等于自己、和零矩陣相乘等于零、和向量相乘得到向量，滿足結合律和分配律，但不滿足交換律。

逆矩陣A^-1：滿足A A^-1= I_n= A^-1A，不可逆的矩陣稱為奇異矩陣。

線性相關：設x1,x2,…,xn是n個向量，若存在不全為零的常系數c2,c2,…,cn，使c1x1+c2x2+…+cnxn=0成立，就稱x1,x2,…,xn線性相關。

非零mXn矩陣A的秩：A的極大線性無關列向量組中向量的個數為列秩，A的極大線性無關行向量組中向量的個數為列秩。任意一個矩陣的行秩和列秩都是相等。mXn的秩是0和min(m,n)之間的一個整數。

非零mXn矩陣A的秩滿足下列條件的最小的數r：存在mXr矩陣B和rXn矩陣C且有A=BC。如果一個nXn的矩陣秩為n，則是滿秩，如果一個mXn矩陣的秩為n，則是列滿秩。

一個方陣滿秩當且僅當它為非奇異矩陣。

當前僅當A無空向量時，矩陣A為列滿秩。

當且僅當A具有空向量時，方陣A是奇異的。

余子式：對于n>1，nXn矩陣A的第ij個余子式是把A的第i行和第j列元素去掉后所形成的一個(n-1)X(n-1)矩陣A_[ij]，表示為det(A_[ij])。

方陣A的行列式具有如下性質：如果A的任何行或列的元素為0，則det(A)=0；用常如a乘A的行列式任意一行（或任意一列）的諸元素，等于用a乘A的行列式；A的行列式中的一行（或一列）元素加上另一行（或另一列）中的相應元素，行列式的值不變；A的行列式值與其轉置矩陣A^T的行列式的值相等；行列式的任意兩行（或兩列）互換，則其值異號。

正定矩陣：nXn矩陣A，如果對所有n維向量x≠0都有x^TAx>0，則矩陣A為正定矩陣。

對任意列滿秩矩陣A，矩陣A^TA是正定的。

1）矩陣乘法的Strassen算法

Strassen算法運用分治法將兩個nXn的矩陣乘積運行時間，從簡易矩陣乘法算法⊙(n³)提升到⊙(n^lg7)= ⊙(n^2.81)。說明算法的主要思想和步驟。

一般情況下，矩陣乘積C=AB，其中A、B和C都是nXn方陣，假定n是2的冪，把A、B和C劃分成四個n/2Xn/2矩陣：

對應四個等式：

r=ae+bg

s=af+bh

t=ce+dg

u=cf+dh

每個等式運行包含兩次n/xXn/2矩陣乘法和兩次乘積所得的n/2Xn/2矩陣的加法運算，推出nXn矩陣相乘所需時間T(n)的遞歸式：T(n)=8T(n/2)+⊙(n²)。

Strassen算法在這個一般性基礎發現，發現只有進行7次n/xXn/2矩陣乘法即可解決，即T(n)=7T(n/2)+⊙(n²)= ⊙(n^lg7)=⊙(n^2.81)，具體算法步驟如下：

第一：輸入矩陣A和B劃分為n/2Xn/2的子矩陣；

第二：運行⊙(n²)標量加法和減法運算，計算出14個n/2Xn/2的矩陣A1,B1,A2,B2,…,A7,B7；

第三：遞歸計算出7個矩陣的乘積P_i=A_iXB_i，i=1,2,…,7；

第四：使用⊙(n²)次標量加法與減法運算，對P_i矩陣的各種組合進行求和或求差運算，從而獲得結果矩陣C的四個子矩陣r\s\t\u。

Strassen算法的核心思想是什么呢？何以產生如此一個步驟的算法呢？依據是什么？

設想每個矩陣的積P_i可以寫成如下形式：

P_i=A_iB_i=(α_i1a+α_i2b+α_i3c+α_i4d)( β_i1e+β_i2f+β_i3g+β_i4h)，其中系數α和β都屬于集合{-1,0,1}，就是說，對矩陣A和B的子矩陣進行加減運算，并對所得的結果進行相乘法來計算出每個子矩陣的乘積。簡單說，將子矩陣的乘法運算變成加減運算，從而將8次乘法減少到7次。這是Strassen算法的核心思想和依據。

算法導論中給出的描述很好理解算法的思路和步驟。正如算法導論中對該算法的討論中所指出的問題，個人對于矩陣乘法的困難（多項式時間內完成的算法）是認同的。Strassen算法并不是最佳，但目前似乎沒有更多的突破。

2）求解線性方程組（LUP分解思想）

求解一組同時成立的線性方程式在很多應用中都會出現，也是線性代數的基本問題?？梢詫⒁粋€線性系統表示為一個矩陣方程，其中每個矩陣或向量元素都屬于一個域，如實數域R。

n個未知量的n個方程用矩陣表示如下：

設A=(a_ij)，x=(x_i)，b=(b_i)，有Ax=b。

如果A是非奇異矩陣（秩為n），存在逆矩陣A^-1，則x= A^-1b，且x是唯一解。方程數目少于未知量數目（或A的秩小于n）為欠定方程組，具有無窮多解，如果方程組不相容則可能無解；方程數目多于未知量數目為超定方程組，可能無解。

LUP分解在求解線性方程組具有數值穩定和速度快的優點。LUP分解的思想就是找出三個nXn矩陣L、U和P，滿足PA=LU，其中L是一個單位下三角矩陣、U是一個上三角矩陣、P是一個置換矩陣。

定義y=Ux，其中x是要求解的未知向量。用正向替換（⊙(n²)）方法求解Ly=Pb，在用逆向替換（⊙(n²)）方法求解Ux=y，可得：

Ax=P^-1LUx==P^-1Ly==P^-1Pb=b

正向替換和逆向替換的方法通過導論中的說明很好理解，問題是如何有效找出LUP呢？只要找出LUP就可以通過正向替換和逆向替換求解x。

LU分解是采用高斯消元法。首先考慮A是nXn的非奇異矩陣，且P等價于I_n，找出A=LU，矩陣L和U稱為A的LU分解。基于LU分解基礎上開展LUP分解，數學基礎一致，不失一般性而已，增加對置換矩陣P中值為1的元素的刻畫。LU和LUP分解的算法要結合案例理解，這里不多描述。最重要還是要對矩陣運算和高斯消元法的數據基礎有初步掌握。

基于LUP分解矩陣求解線性方程組的方法，同樣適用于非奇異矩陣的求逆。矩陣乘法和計算逆矩陣問題具有相同難度的兩個問題，在一定技術條件限制下可以使用一個算法在相同漸進時間內解決另外一個問題，即可用Strassen矩陣乘法算法來求一個矩陣的逆。算法導論中給出了證明以及求解過程描述。

3）最小二乘逼近

先理解對稱正定矩陣的相關性質：任意對稱正定矩陣都是非奇異矩陣；A是一個對稱正定矩陣，則A的每一個主子式都是對稱正定的，關于主子式的Schur補也是對稱正定的；對一個對稱正定矩陣進行LU分解不會出現除數為0的情形。

有了矩陣乘法和矩陣求逆的運算基礎，加上對稱正定矩陣的性質，來看看最小二乘逼近的應用。對給定一組數據的點進行曲線擬合是對稱正定矩陣的重要應用。

總結

以上是生活随笔為你收集整理的算法导论之矩阵运算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。