2022-09-12-「Note」Linear Algebra

被薄纱。。。

听不懂了，好难过。

$\mathbb{Matrix}$

$\mathbb{Definitons}$

对于一个矩阵 $A$ ，主对角线是指 $A_{i, i}$ 上的所有元素。
用 $I$ 表示单位矩阵，即使 $I$ 的主对角线上的所有元素为 $1$ ，其他地方为 $0$。
矩阵的逆是指使得 $A \times P = I$ 的 $P$ 。

$\mathbb{Operation}$

$\mathbb{Addtion}$

点对点加法。

$\mathbb{Multiplication}$

$res_{i, j} = \sum_{k = 1}^{n} A_{i, k} \times B_{k, j}$ 。这就需要 $A$ 的列数和 $B$ 的行数相等。 那么也可以得知，矩阵的乘法满足结合律，而不满足交换律。 ### $\mathbb{Rank}$

一个矩阵的秩是指对于矩阵的线性无关的列向量的个数。
或者讲成是这个矩阵张成空间 $V$ 的维数。

$\mathbb{Code}$

struct Matrix {
  int r, c, a[MAXN][MAXN];
  inline void resize(int _r, int _c) {
    r = _r, c = _c;
    for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++) a[i][j] = 0;
  }
  inline void identity(int _r) {
    r = c = _r;
    for (int i = 1; i <= r; i++) a[i][i] = 1;
  }
  inline Matrix operator * (const Matrix oth) {
    Matrix res; res.resize(oth.r, oth.c);
    for (int k = 1; k <= c; k++)
      for (int i = 1; i <= oth.r; i++)
        for (int j = 1; j <= oth.c; j++) {
          res.a[i][j] = res.a[i][j] + a[i][k] * oth.a[k][j];
        }
    return res;
  }
  inline Matrix operator ^ (int y) const {
    Matrix res; res.identity(r);
    Matrix tmp; tmp.resize(r, c); memcpy(tmp.a, a, sizeof(a));
    while (y) {
      if (y) res = res * tmp;
      tmp = tmp * tmp;
      y >>= 1;
    }
    return res;
  }
};

$\mathbb{Determinant}$

$\mathbb{Definitions}$

对于一个 $n \times n$ 的矩阵 $A$ ，他的行列式写成 $\det(A)$ ，定义为 $\det(A)=\sum_p(-1)^{\tau(p)}\prod_{i=1}^n a_{i,p_i}$ ，其中 $p_i$ 是一个排列， $\tau(p)$ 表示这个排列的逆序对的个数。

然后有一个高级的理解方式是说， $\det(A)$ 表示所有列向量所夹的几何体的有向体积。

关于排列的奇偶性，如果这个排列的逆序对个数是奇数，则这是个奇排列，否则是个偶排列。
那么对于 $n(n \ge 2)$ 个元素的一个元素的排列，奇排列和偶排列出现的次数各占一半。
对于交换这个排列中的两个元素的操作被称为对换，则在一次对换操作后这个排列的奇偶性改变。

这个计算是可以用高斯消元优化的。
首先消成一个上三角，则 $\det(A) = \prod_{i = 1}^n a_{i, i}$

$\mathbb{Nature}$

$$ \det(A) = \det(A^T) \tag{1} $$ $$ \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ ka_{i,1}&ka_{i,2}&\dots&ka_{i,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| = k \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ a_{i,1}&a_{i,2}&\dots&a_{i,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| \tag{2} $$ $$ \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ b_{i,1}+c{i,1}&b_{i,2}+c{i,2}&\dots&b_{i,n}+c{i,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| = \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ b_{i,1}&b_{i,2}&\dots&b_{i,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| + \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ c_{i,1}&c_{i,2}&\dots&c_{i,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| \tag{3} $$ $$ \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ a_{j,1}&a_{j,2}&\dots&a_{j,n} \\ \dots&\dots&\dots&\dots\\ a_{k,1}&a_{k,2}&\dots&a_{k,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| =- \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ a_{k,1}&a_{k,2}&\dots&a_{k,n} \\ \dots&\dots&\dots&\dots\\ a_{j,1}&a_{j,2}&\dots&a_{j,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| \tag{4} $$ $$ \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ a_{i,1}&a_{i,2}&\dots&a_{i,n} \\ \dots&\dots&\dots&\dots\\ ka_{i,1}&ka_{i,2}&\dots&ka_{i,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| = k\times \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ a_{i,1}&a_{i,2}&\dots&a_{i,n} \\ \dots&\dots&\dots&\dots\\ a_{i,1}&a_{i,2}&\dots&a_{i,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| = 0 \tag{5} $$ $$ \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ a_{i,1}&a_{i,2}&\dots&a_{i,n} \\ \dots&\dots&\dots&\dots\\ ka_{i,1}+a_{j,1}&ka_{i,2}+a_{j,2}&\dots&ka_{i,n}+a_{j,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| = \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ a_{i,1}&a_{i,2}&\dots&a_{i,n} \\ \dots&\dots&\dots&\dots\\ a_{j,1}&a_{j,2}&\dots&a_{j,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| + \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ a_{i,1}&a_{i,2}&\dots&a_{i,n} \\ \dots&\dots&\dots&\dots\\ ka_{i,1}&ka_{i,2}&\dots&ka_{i,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| \\ = \left |\begin{array}{cccc} a_{1,1}&a_{1,2}&\dots&a_{1,n} \\ \dots&\dots&\dots&\dots\\ a_{i,1}&a_{i,2}&\dots&a_{i,n} \\ \dots&\dots&\dots&\dots\\ a_{j,1}&a_{j,2}&\dots&a_{j,n} \\ \dots&\dots&\dots&\dots\\ a_{n,1}&a_{n,2}&\dots&a_{n,n} \\ \end{array}\right| \tag{6} $$