矩阵运算作为线性代数里面的一个知识点，在ACM竞赛中也有非常大的用处。 ## 矩阵的定义 矩阵的一般表示形式为： ~~~[math] \begin{bmatrix} a_{11} & a_{12} & ... & ... & a_{1m}\\ a_{21} & a_{22} & ... & ... & a_{2m}\\ ... & ... & ... & ... & ...\\ a_{n1} & a_{n2} & ... & ... & a_{nm} \end{bmatrix} ~~~ 矩阵的元素用一个中括号包括起来，上面这个式子表示的即为大小为n*m的矩阵。 当n=m时，这个矩阵也被称为n阶矩阵。 ## 矩阵运算 ### 矩阵加减法 矩阵加减法的前提是**两个矩阵的行和列相等**，比如下面这个两个式子： 加法： ~~~[math] \begin{bmatrix} 1 & 4 & 2 \\ 2 & 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 & 5 \\ 7 & 5 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 4 & 7 \\ 9 & 5 & 0 \end{bmatrix} ~~~ 减法： ~~~[math] \begin{bmatrix} 1 & 4 & 2 \\ 2 & 0 & 0 \end{bmatrix} - \begin{bmatrix} 0 & 0 & 5 \\ 7 & 5 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 4 & -3 \\ -5 & -5 & 0 \end{bmatrix} ~~~ ### 矩阵的转置 将矩阵的行和列互相调换即为矩阵的转置，比如下面的式子： ~~~[math] {\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}}^T = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} ~~~ ### **矩阵乘法** 矩阵乘法是重点要讲的，在ACM竞赛中使用最多的也是矩阵的乘法运算，尤其是矩阵快速幂。 两个矩阵相乘的前提条件为第一个矩阵的**列数**和第二个矩阵的**行数**必须相等！比如下面这个式子： ~~~[math] \begin{bmatrix} a_{11} & a_{12} & ... & a_{1k} \\ a_{21} & a_{22} & ... & a_{2k} \\ ... & ... & ... & ...\\ a_{n1} & a_{n2} & ... & a_{nk} \end{bmatrix} * \begin{bmatrix} b_{11} & b_{12} & ... & b_{1m} \\ b_{21} & b_{22} & ... & b_{2m} \\ ... & ... & ... & ...\\ b_{k1} & b_{k2} & ... & b_{km} \end{bmatrix} = \begin{bmatrix} c_{11} & c_{12} & ... & c_{1m} \\ c_{21} & c_{22} & ... & c_{2m} \\ ... & ... & ... & ...\\ c_{n1} & c_{n2} & ... & c_{nm} \end{bmatrix} ~~~ 这是矩阵运算的基本形式，接下来我们看如何具体运算。 ~~~[math] c_{i,j}=a_{i1}*b{1j}+a_{i2}*b{2j}+...+a_{ik}*b_{kj}=\sum_{x=1}^{k}{a_{ix}*b_{xj}} ~~~ 其中的k也就是第一个矩阵的列数和第二个矩阵的行数。 带入具体矩阵运算： ~~~[math] \begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix} * \begin{bmatrix} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} {(1*3+0*2+2*1)} & {(1*1+0*1+2*0)} \\ {(-1*3+3*2+1*1)} & {(-1*1+3*1+1*0)} \end{bmatrix} = \begin{bmatrix} 5 & 1 \\ 4 & 2 \end{bmatrix} ~~~