线性代数

亿方通行 · 2021-04-05 09:27:19 · 个人记录

矩阵的定义

由 m\times n 个数 a_{i,j} 排成的 m 行 n 列的数表称为 m 行 n 列的矩阵，简称 m\times n 矩阵。

A = \begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\a_{2,1}&a_{2,2}&\cdots&a_{2,n}\\a_{3,1}&a_{3,2}&\cdots&a_{3,n}\\\vdots&\vdots&\ddots&\vdots\\a_{m,1}&a_{m,2}&\cdots&a_{m,n}\end{bmatrix}

行数与列数都等于 n 的矩阵称为 n 阶矩阵或 n 阶方阵。

矩阵加法

若

C = A +B

则

C_{i,j} = A_{i,j} + B_{i,j}

矩阵减法

若

C = A -B

则

C_{i,j} = A_{i,j} - B_{i,j}

矩阵数乘

若

C = k\times A

则

C_{i,j} =k\times A_{i,j}

矩阵乘法

若

C=A\times B

则

C_{i,j} = \sum\limits_{k=1}^na_{i,k}b_{k,j}

一个 n\times k 的矩阵和一个 k\times m 的矩阵相乘，得到一个 n\times m 的矩阵。
用途——优化线性递推

构造一个 n 阶矩阵 A ，使得：

A\times B_i = B_{i+1}

那么

A^{k-1}\times B_1 = B_k

其中 A^{k-1} 可以用快速幂求解，时间复杂度为 O(n^3logk)。

用线性代数相关知识 + FFT 可以将线性递推的时间复杂度优化到 O(nlognlogk)。

矩阵行列式

一个 n 阶矩阵的行列式记为 \left\vert A \right\vert 或 \det A。

一个 2\times 2 矩阵的行列式可表示如下：

\det\begin{pmatrix}a&b\\c&d\end{pmatrix}=ad-bc

一个 n 阶矩阵的行列式等于其任意行（或列）的元素与对应的代数余子式乘积之和，即：

\det(A) = \sum\limits_{j=1}^n(-1)^{i+j}a_{i,j}\det(A_{i,j})

其中， A_{i,j} 表示 A 去掉第 i 行第 j 列后所构成矩阵的行列式。

n 阶矩阵某两行（列）交换，行列式 \times (-1)。
矩阵某一行（列）加上或减去另一行（列），行列式不变。
矩阵某一行（列） \times k ，行列式 \times k。

高斯消元

bool Gauss(){
    for(int i=1;i<=n;i++){
        int mx=i;
        for(int j=i+1;j<=n;j++) if(fabs(M[j][i])>fabs(M[mx][i])) mx=j;
        for(int j=1;j<=n+1;j++) swap(M[i][j],M[mx][j]);
        if(fabs(M[i][i])<=1e-7) return 0;
        for(int j=1;j<=n;j++) if(j!=i){
            double tmp=M[j][i]/M[i][i];
            for(int k=i+1;k<=n+1;k++) M[j][k]-=M[i][k]*tmp;
        }
    }
    for(int i=1;i<=n;i++) M[i][n+1]/=M[i][i],M[i][i]=1;
    return 1;
}