526互联

2022-09-12-Linear Algebra

发布时间 2023-07-05 15:42:45作者: Iridescent41

被薄纱。。。

听不懂了，好难过。

\(\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} \]