C/C++教程

线性代数小trick

本文主要是介绍线性代数小trick,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

线性代数小trick

  1. 行列式
    ∣ a i j ∣ n |a_i^j|_n ∣aij​∣n​ = ∣ a 1 1 . . . a 1 n . . . a n 1 . . . a n n ∣ \begin{vmatrix} a_1^1&...&a_1^n \\ &...\\ a_n^1&...&a_n^n \end{vmatrix} ∣∣∣∣∣∣​a11​an1​​.........​a1n​ann​​∣∣∣∣∣∣​
    n n n个元素构成的 n n n阶行列式:
    通式: a [ i , j ] n = a[i,j]n= a[i,j]n= ∑ j 1 , j 2 . . . j n ( − 1 ) r ( j 1 , j 2 , . . . , j n ) a 1 j 1 a 2 j 2 . . . a n j n \sum_{j_{1},j_{2}...j_{n}}(-1)^{r(j_{1},j_{2},...,j_{n})}a_{1j_{1}}a_{2j_{2}}...a_{nj_{n}} ∑j1​,j2​...jn​​(−1)r(j1​,j2​,...,jn​)a1j1​​a2j2​​...anjn​​ r ( j 1 , j 2 , . . . j n ) r(j_{1},j_{2},...j_{n}) r(j1​,j2​,...jn​)表示逆序对个数。 行列式的某些性质:
    1. 1. 1. a [ i , j ] n = a [ j , i ] n a[i,j]n=a[j,i]n a[i,j]n=a[j,i]n。(行与列交换后的转置行列式和原行列式相同)
    说真的,我找遍了全网,都没找到一个让我满意的证明。于是,献上一份我自己理解的行列变换后行列式值不变的证明(数形结合):
    首先,这是一种情况:在这里插入图片描述
    我们想一下,求逆序对个数,我们就图像来看怎么求?
    是不是对于每个黑块,我们都要求出它右上方有多少个黑块,那么,它对逆序对个数的贡献就是它的右上和左下方的黑方块数(因为它既与右上的黑方块构成逆序对,又与左下的黑方块构成逆序对)。
    将其翻转后,图像是这样的:
    在这里插入图片描述
    对于上图的逆序对个数,我们还是要求每一个黑方块的右上和左下有多少黑方块,然后,我们就会惊奇地发现,变换后图像中,每一个方块的右上就对应了变换前每一个方块的左下,也就是说,二者等价!!!这样,就可以证明性质1了。
    2. 2. 2.交换行列式任意两行,得到 a [ i , j ] n ∗ a[i,j]n* a[i,j]n∗, a [ i , j ] n = − a [ i , j ] n ∗ a[i,j]n=-a[i,j]n* a[i,j]n=−a[i,j]n∗,
    这是因为:对于一组数: i , a 1 , a 2 , a 3 . . a n , j i,a_{1},a_{2},a_{3}..a_{n},j i,a1​,a2​,a3​..an​,j, i ! = j i!=j i!=j,将 i i i与 j j j交换,逆序对个数奇偶性相反。
    3. 3. 3.行列式中的每一行都乘上k,得到的结果是原来的k倍。
    4. 4. 4.对于两个行列式 a , b a,b a,b,若只有第 i i i行不同,那么两者之和为一个新的矩阵的行列式,这个矩阵的第 i i i行的对应值为 a i + b i a_{i}+b_{i} ai​+bi​,其他行的值与原来相同,根据加法原理。
    5. 5. 5.一个矩阵中,若某两行 i , j i,j i,j完全相同,那这个矩阵的行列式为 0 0 0,根据性质2可得。
    6. 6. 6.一个矩阵,若某两行: i , j i,j i,j,变换为: a [ j ] = a [ j ] + k ∗ a [ i ] a[j]=a[j]+k*a[i] a[j]=a[j]+k∗a[i],行列式的值不变。根据性质4和性质5可证。
  2. 代数余子式
    在 n n n 阶行列式 D D D 中划去任意选定的 k k k 行、 k ( 0 < k < n ) k (0 < k < n) k(0<k<n)列后,余下的元素按原来顺序组成的 n − k n - k n−k 阶行列式 M M M ,称为 M M M 是其中一个行列式 D D D 的 k k k 阶余子式。
    主子式:去掉的行和列相同。
  3. 范德蒙德行列式
    D n D_n Dn​ = ∣ 1 1 . . . 1 x 1 x 2 . . . x n x 1 2 x 2 2 . . . x n 2 . . . x 1 n x 2 n . . . x n n ∣ \begin{vmatrix} 1&1&...&1 \\ x_1&x_2&...&x_n\\ x_1^2&x_2^2&...&x_n^2\\ &...\\ x_1^n&x_2^n&...&x_n^n \end{vmatrix} ∣∣∣∣∣∣∣∣∣∣​1x1​x12​x1n​​1x2​x22​...x2n​​............​1xn​xn2​xnn​​∣∣∣∣∣∣∣∣∣∣​ = ∏ 1 < = i < j < = n ( x j − x i ) \prod_{1<=i<j<=n}(x_j-x_i) ∏1<=i<j<=n​(xj​−xi​).
    证:
    首先,若 n = 2 n=2 n=2时,此式一定成立。
    对于 D n D_n Dn​,我们先假设 D n − 1 D_{n-1} Dn−1​是正确的,那么,如果我们可以证出来 D n D_n Dn​满足范德蒙德行列式的形式,则证明范德蒙德行列式正确。我们要利用行列式的性质对 D n D_n Dn​做出一些基本变换:
    将 D n D_n Dn​的每一行(除第一行外)都减去上一行的对应值乘上 x n x_n xn​,由行列式性质可得,变换后的行列式与原来相同。
    D n D_n Dn​= ∣ 1 1 . . . 1 x 1 − x n x 2 − x n . . . x n − x n x 1 2 − x 1 x n x 2 2 − x 2 x n . . . x n 2 − x n x n . . . x 1 n − x 1 n − 1 x n x 2 n − x 2 n − 1 x n . . . x n n − x n n − 1 x n ∣ \begin{vmatrix} 1&1&...&1 \\ x_1-x_n&x_2-x_n&...&x_n-x_n\\ x_1^2-x_1x_n&x_2^2-x_2x_n&...&x_n^2-x_nx_n\\ &...\\ x_1^n-x_1^{n-1}x_n&x_2^n-x_2^{n-1}x_n&...&x_n^n-x_n^{n-1}x_n \end{vmatrix} ∣∣∣∣∣∣∣∣∣∣​1x1​−xn​x12​−x1​xn​x1n​−x1n−1​xn​​1x2​−xn​x22​−x2​xn​...x2n​−x2n−1​xn​​............​1xn​−xn​xn2​−xn​xn​xnn​−xnn−1​xn​​∣∣∣∣∣∣∣∣∣∣​
    =
                 \;\;\;\;\;\; ∣ 1 1 . . . 1 x 1 − x n x 2 − x n . . . 0 x 1 2 − x 1 x n x 2 2 − x 2 x n . . . 0 . . . x 1 n − x 1 n − 1 x n x 2 n − x 2 n − 1 x n . . . 0 ∣ \begin{vmatrix} 1&1&...&1 \\ x_1-x_n&x_2-x_n&...&0\\ x_1^2-x_1x_n&x_2^2-x_2x_n&...&0\\ &...\\ x_1^n-x_1^{n-1}x_n&x_2^n-x_2^{n-1}x_n&...&0 \end{vmatrix} ∣∣∣∣∣∣∣∣∣∣​1x1​−xn​x12​−x1​xn​x1n​−x1n−1​xn​​1x2​−xn​x22​−x2​xn​...x2n​−x2n−1​xn​​............​1000​∣∣∣∣∣∣∣∣∣∣​
    那么,根据行列式的通项式,只有第一行选择n时,才会对答案产生贡献。
    设 D ∗ D^* D∗= ∣ x 1 − x n x 2 − x n . . . x n − 1 − x n x 1 2 − x 1 x n x 2 2 − x 2 x n . . . x n − 1 2 − x n − 1 x n . . . x 1 n − x 1 n − 1 x n x 2 n − x 2 n − 1 x n . . . x n − 1 n − x n − 1 n − 1 x n ∣ \begin{vmatrix} x_1-x_n&x_2-x_n&...&x_{n-1}-x_n\\ x_1^2-x_1x_n&x_2^2-x_2x_n&...&x_{n-1}^2-x_{n-1}x_n\\ &...\\ x_1^n-x_1^{n-1}x_n&x_2^n-x_2^{n-1}x_n&...&x_{n-1}^n-x_{n-1}^{n-1}x_n \end{vmatrix} ∣∣∣∣∣∣∣∣​x1​−xn​x12​−x1​xn​x1n​−x1n−1​xn​​x2​−xn​x22​−x2​xn​...x2n​−x2n−1​xn​​.........​xn−1​−xn​xn−12​−xn−1​xn​xn−1n​−xn−1n−1​xn​​∣∣∣∣∣∣∣∣​
    D n = ( − 1 ) n − 1 D ∗ D_n=(-1)^{n-1}D^* Dn​=(−1)n−1D∗,这是因为,对于 1 — n − 1 1—n-1 1—n−1的每一个排列,最前面都会插入一个 n n n,逆序对个数增加 n − 1 n-1 n−1个,若 n − 1 n-1 n−1是奇数,逆序对个数的奇偶性会改变;否则,不会改变。
    所以:
    D n = ( − 1 ) n − 1 ∗ D_n=(-1)^{n-1}* Dn​=(−1)n−1∗ ∣ x 1 − x n x 2 − x n . . . x n − 1 − x n x 1 2 − x 1 x n x 2 2 − x 2 x n . . . x n − 1 2 − x n − 1 x n . . . x 1 n − x 1 n − 1 x n x 2 n − x 2 n − 1 x n . . . x n − 1 n − x n − 1 n − 1 x n ∣ \begin{vmatrix} x_1-x_n&x_2-x_n&...&x_{n-1}-x_n\\ x_1^2-x_1x_n&x_2^2-x_2x_n&...&x_{n-1}^2-x_{n-1}x_n\\ &...\\ x_1^n-x_1^{n-1}x_n&x_2^n-x_2^{n-1}x_n&...&x_{n-1}^n-x_{n-1}^{n-1}x_n \end{vmatrix} ∣∣∣∣∣∣∣∣​x1​−xn​x12​−x1​xn​x1n​−x1n−1​xn​​x2​−xn​x22​−x2​xn​...x2n​−x2n−1​xn​​.........​xn−1​−xn​xn−12​−xn−1​xn​xn−1n​−xn−1n−1​xn​​∣∣∣∣∣∣∣∣​
    再将上式进行变换:
    D n = ( − 1 ) n − 1 ∗ D_n=(-1)^{n-1}* Dn​=(−1)n−1∗ ∣ x 1 − x n x 2 − x n . . . x n − 1 − x n x 1 ( x 1 − x n ) x 2 ( x 2 − x n ) . . . x n − 1 ( x n − 1 − x n ) . . . x 1 n − 1 ( x 1 − x n ) x 2 n − 1 ( x 2 − x n ) . . . x n − 1 n − 1 ( x n − 1 − x n ) ∣ \begin{vmatrix} x_1-x_n&x_2-x_n&...&x_{n-1}-x_n\\ x_1(x_1-x_n)&x_2(x_2-x_n)&...&x_{n-1}(x_{n-1}-x_n)\\ &...\\ x_1^{n-1}(x_1-x_n)&x_2^{n-1}(x_2-x_n)&...&x_{n-1}^{n-1}(x_{n-1}-x_n) \end{vmatrix} ∣∣∣∣∣∣∣∣​x1​−xn​x1​(x1​−xn​)x1n−1​(x1​−xn​)​x2​−xn​x2​(x2​−xn​)...x2n−1​(x2​−xn​)​.........​xn−1​−xn​xn−1​(xn−1​−xn​)xn−1n−1​(xn−1​−xn​)​∣∣∣∣∣∣∣∣​,
    根据性质一和性质三,再进行变换:
    D n = ( − 1 ) n − 1 ∗ ( x 1 − x n ) ( x 2 − x n ) . . . ( x n − 1 − x n ) ∗ D_n=(-1)^{n-1}*(x_1-x_n)(x_2-x_n)...(x_{n-1}-x_n)* Dn​=(−1)n−1∗(x1​−xn​)(x2​−xn​)...(xn−1​−xn​)∗ ∣ 1 1 . . . 1 x 1 x 2 . . . x n − 1 . . . x 1 n − 1 x 2 n − 1 . . . x n − 1 n − 1 ∣ \begin{vmatrix} 1&1&...&1\\ x_1&x_2&...&x_{n-1}\\ &...\\ x_1^{n-1}&x_2^{n-1}&...&x_{n-1}^{n-1} \end{vmatrix} ∣∣∣∣∣∣∣∣​1x1​x1n−1​​1x2​...x2n−1​​.........​1xn−1​xn−1n−1​​∣∣∣∣∣∣∣∣​,
    再观察,后面这个行列式不就是 D n − 1 D_{n-1} Dn−1​吗!
    ( − 1 ) n − 1 ∗ ( x 1 − x n ) ( x 2 − x n ) . . . ( x n − 1 − x n ) (-1)^{n-1}*(x_1-x_n)(x_2-x_n)...(x_{n-1}-x_n) (−1)n−1∗(x1​−xn​)(x2​−xn​)...(xn−1​−xn​)又可变为:
    ( x n − x 1 ) ( x n − x 2 ) . . . ( x n − x n − 1 ) (x_n-x_1)(x_n-x_2)...(x_n-x_{n-1}) (xn​−x1​)(xn​−x2​)...(xn​−xn−1​),
    最终式:
    D n = ( x n − x 1 ) ( x n − x 2 ) . . . ( x n − x n − 1 ) ∗ D_n=(x_n-x_1)(x_n-x_2)...(x_n-x_{n-1})* Dn​=(xn​−x1​)(xn​−x2​)...(xn​−xn−1​)∗ ∣ 1 1 . . . 1 x 1 x 2 . . . x n − 1 . . . x 1 n − 1 x 2 n − 1 . . . x n − 1 n − 1 ∣ \begin{vmatrix} 1&1&...&1\\ x_1&x_2&...&x_{n-1}\\ &...\\ x_1^{n-1}&x_2^{n-1}&...&x_{n-1}^{n-1} \end{vmatrix} ∣∣∣∣∣∣∣∣​1x1​x1n−1​​1x2​...x2n−1​​.........​1xn−1​xn−1n−1​​∣∣∣∣∣∣∣∣​,
    又因 D n − 1 D_{n-1} Dn−1​已满足范德蒙德行列式,所以 D n D_n Dn​可证得,也满足范德蒙德行列式。
这篇关于线性代数小trick的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!