矩阵是数字或 “元素” 的矩形阵列。当矩阵 $A$ 有 $m$ 行 $n$ 列，则是一个 $m\times n$ 的矩阵。如果矩阵的形状相同，则它们可以相加。矩阵也可以乘上任意常数 $c$。以下是 $A+B$ 和 $2A$ 的例子，它们都是 $3\times 2$ 的矩阵：$$\left[\begin{array}{cc}1& 2\\ 3& 4\\ 0& 0\end{array}\right]+\left[\begin{array}{cc}2& 2\\ 4& 4\\ 9& 9\end{array}\right]=\left[\begin{array}{cc}3& 4\\ 7& 8\\ 9& 9\end{array}\right],2\left[\begin{array}{cc}1& 2\\ 3& 4\\ 0& 0\end{array}\right]=\left[\begin{array}{cc}2& 4\\ 6& 8\\ 0& 0\end{array}\right]$$矩阵的加法和向量的加法一样，每次处理一个元素。我们也可以将列向量看成是只有一列的矩阵（$n=1$）。$-A$ 可以看成是 $c$ 乘矩阵 $A$（$c=-1$），它与 $A$ 中全部元素的符号都相反。$A$ 加上 $-A$ 是零矩阵，它的全部元素均为零。这些是基础知识，下面将考虑矩阵的乘法。

一、第一种方法：单个元素的计算

第 $i$ 行第 $j$ 列的元素记为 $a_{ij}$ 或 $A(i,j)$，第一行的 $n$ 个元素分别记为 $a_{11},a_{12},\cdots ,a_{1n}$。左下角的元素是 $a_{m1}$，右下角的元素是 $a_{mn}$。行的数字 $i$ 从 $1$ 到 $m$，列的数字 $j$ 从 $1$ 到 $n$。
若矩阵 $A$ 和 $B$ 可以相乘时，这里总共讨论 $4$ 种方法求 $AB$。矩阵 $A$ 和 $B$ 相乘需要满足如下条件：
$AB$ 可以相乘： 若 $A$ 有 $n$ 列，则 $B$ 必须由 $n$ 行
当 $A$ 是 $3\times 2$ 的矩阵时，$B$ 可以是 $2\times 1$（向量）、$2\times 2$（方阵）或 $2\times 20$ 的矩阵，必须是 $2$ 行，但是不可以是 $3\times 2$ 的矩阵。$A$ 乘数 $B$ 的每一列。 第一种矩阵相乘的方法是点积的方式，矩阵的乘法遵守以下法则：$$矩阵乘法的基础法则AB乘C等于A乘BC(\mathrm{2.4.1})$$括号可以在 $ABC$ 之间安全移动，$(AB)C=A(BC)$，线性代数也是基于这个法则。
假设 $A$ 是 $m\times n$ 的矩阵，$B$ 是 $n\times p$ 的矩阵，它们可以相乘，乘积 $AB$ 是 $m\times p$ 的矩阵。$$(m\times n)\times (n\times p)=(m\times p),\left[\begin{array}{c}m\text{rows}\\ ncolumns\end{array}\right]\left[\begin{array}{c}nrows\\ p\text{columns}\end{array}\right]=\left[\begin{array}{c}m\text{rows}\\ p\text{columns}\end{array}\right]$$一行乘一列是一种极端的情况，$1\times n$ 乘 $n\times 1$ 的结果是 $1\times 1$，这个数字就是点积。
任何情况下 $AB$ 中的元素都是点积，$AB$ 左上角的元素 $(1,1)$ 是 $(A的行1)\cdot (B的列1)$。这就是第一种计算方法，是矩阵乘法常用的方法。计算 $A$ 的每一行和 $B$ 的每一列的点积。$$1.AB的行i列j元素是(A的行i)\cdot (B的列j)$$Figure 2.8 是 $4\times 5$ 矩阵 $A$ 的第二行 $(i=2)$，$5\times 6$ 矩阵 $B$ 的第三列 $(j=3)$，它们的点积在 $AB$ 的行 $2$ 列 $3$。矩阵 $AB$ 的行数与 $A$ ($4$ 行)相同，列数与 $B$（$6$ 列）相同。

【例1】当且仅当方阵（Square matrices）的大小相同时，它们才可以相乘：$$\left[\begin{array}{cc}1& 1\\ 2& -1\end{array}\right]\left[\begin{array}{cc}2& 2\\ 3& 4\end{array}\right]=\left[\begin{array}{cc}5& 6\\ 1& 0\end{array}\right]$$第一个点积是 $1\cdot 2+1\cdot 3=5$，其它三个点积可以通过同样的方法计算。每个点积需要两次乘法，总共是 $8$ 次。
如果 $A$ 和 $B$ 都是 $n\times n$ 的方阵，则 $AB$ 也是 $n\times n$ 的方阵，它包含 $n^2$ 次点积，即 $A$ 的行数乘 $B$ 的列数。每一个点积需要 $n$ 次乘法，所以计算 $AB$ 总共需要 $n^3$ 次乘法。当 $n=100$ 时，需要 $100^3=1000000$ 次乘法；当 $n=2$ 时，需要 $2^3=8$ 次乘法。
目前有人找到只需要 $7$ 次（会有额外的加法）的方法。但是比较难以处理，所以目前仍认为正常的科学计算需要 $n^3$ 次。

【例2】假设 $A$ 是一个行向量（$1\times 3$），$B$ 是一个列向量（$3\times 1$），则 $AB$ 是 $1\times 1$（仅有一个点积，一个元素）。若反过来相乘，$BA$（一列乘一行）则会得到一个完整的 $3\times 3$ 矩阵，这样的乘法也是允许的！$$\begin{array}{c}列乘行\\ (n\times 1)(1\times n)=(n\times n)\end{array}\left[\begin{array}{c}0\\ 1\\ 2\end{array}\right]\left[\begin{array}{ccc}1& 2& 3\end{array}\right]=\left[\begin{array}{ccc}0& 0& 0\\ 1& 2& 3\\ 2& 4& 6\end{array}\right]$$一行乘一列是内积（inner product），这是点积的另一个名称。一列乘一行是外积（outer product）。这是一些矩阵乘法的极端情况。

二、第二和第三种方法：行和列

在大图（big picture）中，$A$ 乘 $B$ 的每一列，结果是 $AB$ 的一列，该列是 $A$ 列的组合。$AB$ 的每一列都是 $A$ 列的线性组合。这是矩阵乘法的列图像：$$2.矩阵A乘B的每一列A[b_1\cdots b_p]=[A{b}_1\cdots A{b}_p]$$行图像则相反，$A$ 的每一行乘整个矩阵 $B$ 是 $AB$ 的一行。$AB$ 的每一行都是 $B$ 行的线性组合：$$3.A的每一行乘矩阵B[A的行i]\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right]=[AB的行i]$$消元法中用到的是行运算（$E乘A$），$A{A}^{-1}$ 中用到的是列运算。“行-列图像” 有行与列的点积，手算矩阵时经常使用点积：有 $mnp$ 次乘法/加法 步骤。$$AB=(m\times n)(n\times p)=(m\times p),+mp次点积，每次点积需要n个步骤(\mathrm{2.4.2})$$

三、第四种方法：列乘行

矩阵的第四种乘法是列乘行，然后将其相加：$$4.A的列1至列n，乘B的行1至行n，将全部矩阵相加$$$A$ 的列 $1$ 乘 $B$ 的行 $1$，$A$ 的列 $2,3$ 乘 $B$ 的行 $2,3$，然后相加：$$\left[\begin{array}{ccc}\text{col}1& \text{col2}& \text{col3}\\ \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot \end{array}\right]\left[\begin{array}{ccc}\text{row1}& \cdots & \\ \text{row2}& \cdots & \\ \text{row3}& \cdots & \end{array}\right]=(\text{col1})(\text{row1})+\text{(col2)(row2)+(col3)(row3)}$$当 $A$ 和 $B$ 均是 $2\times 2$ 的矩阵时$$AB=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]\left[\begin{array}{cc}E& F\\ G& H\end{array}\right]=\left[\begin{array}{cc}aE+bG& aF+bH\\ cE+dG& cF+dH\end{array}\right]$$$$A的列乘B的行，再相加AB=\left[\begin{array}{c}a\\ c\end{array}\right]\left[\begin{array}{cc}E& F\end{array}\right]+\left[\begin{array}{c}b\\ d\end{array}\right]\left[\begin{array}{cc}G& H\end{array}\right](\mathrm{2.4.3})$$$A$ 的列 $k$ 乘 $B$ 的行 $k$ 得到一个矩阵，令 $k=1,2,\cdots ,n$，然后将所有的矩阵相加得到 $AB$。
如果 $AB$ 是 $(m\times n)(n\times p)$，则 $n$ 个矩阵都是列与行相乘的 $m\times p$ 矩阵。该方法同样需要 $mnp$ 次乘法，只是顺序不同。

四、矩阵运算法则

矩阵运算遵循以下六个法则，还有一个法则是不正确的。矩阵可以是方形的也可以是矩形的。下面是三个加法法则：$$\begin{array}{cc}A+B=B+A& (交换律\text{commutativelaw})\\ c(A+B)=cA+cB& (分配律\text{distributivelaw})\\ A+(B+C)=(A+B)+C& (结合律\text{associativelaw})\end{array}$$另外三个法则是乘法法则，注意 $AB=BA$ 通常来说都是错误的：$$\begin{array}{cc}AB\ne BA& (交换律通常不成立)\\ A(B+C)=AB+AC& (左分配律)\\ (A+B)C=AC+BC& (右分配律)\\ A(BC)=A(BC)& (ABC的结合律)(不需要括号)\end{array}$$当 $A$ 和 $B$ 不是方阵时，$AB$ 和 $BA$ 的大小不同，也不可能相等（假设可以相乘）。对于方阵，绝大部分情况都有 $AB\ne BA$：$$AB=\left[\begin{array}{cc}0& 0\\ 1& 0\end{array}\right]\left[\begin{array}{cc}0& 1\\ 0& 0\end{array}\right]=\left[\begin{array}{cc}0& 0\\ 0& 1\end{array}\right],但是BA=\left[\begin{array}{cc}0& 1\\ 0& 0\end{array}\right]\left[\begin{array}{cc}0& 0\\ 1& 0\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 0& 0\end{array}\right]$$$AI=IA$ 是成立的，所有的方阵与 $I$ 相乘都满足交换律，与 $cI$ 也一样。只有这些矩阵的乘法顺序才可交换。
法则 $A(B+C)=AB+AC$ 可以一次证明一列。对于第一列 $A(\mathbf{b}+\mathbf{c})=A\mathbf{b}+A\mathbf{c}$，这个是所有事情的关键 —— 线性。
法则 $A(BC)=(AB)C$ 表示可以先乘 $BC$ 也可以先乘 $AB$，这个法则很有用，是矩阵乘法的关键。
当 $A=B=C$ 且为方阵时，$(A$ 乘 $A^2)$ 等于 $(A^2$ 乘 $A)$。它们的乘积都是 $A^3$。矩阵的幂 $A^p$ 和数字的运算法则一致：$$A^p=AAA\cdots A(p个因子)(A^p)(A^q)=A^{p+q}(A^p{)}^q=A^{pq}$$这是指数的一般法则，$A^3$ 乘 $A^4$ 是 $A^7$，$A^3$ 的 $4$ 次方是 $A^{12}$。当 $p$ 和 $q$ 是零或负数时，这个法则任然成立。假设 $A$ 有 $-1$ 次方 —— 逆矩阵 $A^{-1}$。$A^0=I$ 是单位矩阵，类似 $2^0=1$。
对于数字 $a^{-1}=1/a$，对矩阵来说逆矩阵写成 $A^{-1}$（不是 $I/A$，除了MATLAB）。除了 $a=0$ 以外的数都有倒数，但是对于矩阵 $A$ 有没有逆矩阵是线性代数的核心问题。

五、分块矩阵与分块乘法

矩阵可以被分割成块（blocks，小一些的矩阵）。下面是一个 $4\times 6$ 的矩阵，分割成 $2\times 2$ 的块，本例中每个块都是单位矩阵 $I$：$$\begin{array}{c}4\times 6的矩阵分成\\ 2\times 2的分块矩阵\\ 得到2\times 3个分块矩阵\end{array}A=\left[\begin{array}{cccccc}1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 1\end{array}\right]=\left[\begin{array}{ccc}I& I& I\\ I& I& I\end{array}\right]$$如果 $B$ 也是 $4\times 6$ 的矩阵，且大小匹配，则可以对 $A+B$ 匹配的方块相加。
将 $\mathbf{b}$ 放在 $A$ 旁边就变成增广矩阵，$\left[\begin{array}{cc}A& \mathbf{b}\end{array}\right]$ 有两个大小不一样的方块，这也是分块矩阵，左乘上消元矩阵得到 $\left[\begin{array}{cc}EA& E\mathbf{b}\end{array}\right]$。只要形状匹配，那么分块相乘就没有问题。$$\begin{gathered} 分块乘法:如果A的分块可以乘B的分块，那么AB就可以分块相乘。A的列分割必须和B的行分割相匹配。 \\ \left[\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right]\left[\begin{array}{c}{B}_{11}\\ B_{21}\end{array}\right]=\left[\begin{array}{c}{A}_{11}{B}_{11}+A_{12}{B}_{21}\\ A_{21}{B}_{11}+A_{22}{B}_{21}\end{array}\right](\mathrm{2.4.4}) \end{gathered}$$若每个分块都是数字（$1\times 1$ 的矩阵），这种特殊情况就是矩阵的乘法，它们是一致的。上式所有的 $A$ 都要放在 $B$ 之前，因为 $AB$ 与 $BA$ 是不同的。
重点： 当对矩阵进行分块时，经常更容易看出它们如何作用的。如上例中分块矩阵是单位矩阵 $I$ 就比原来的 $4\times 6$ 的矩阵更清晰。

【例3】（重要的特殊情况）将矩阵 $A$ 每列分成一块，共 $n$ 列，矩阵 $B$ 每行分成一块，共 $n$ 行，则 $AB$ 的分块乘法就是列乘行相加：$$列乘行\left[\begin{array}{ccc}|& & |\\ a_1& \cdots & a_n\\ |& & |\end{array}\right]\left[\begin{array}{ccc}-& b_1& -\\ & \cdots & \\ -& b_n& -\end{array}\right]=\left[\begin{array}{c}{a}_1{b}_1+\cdots +a_n{b}_n\end{array}\right](\mathrm{2.4.5})$$这就是第四种矩阵乘法。下面是具体的例子：$$\left[\begin{array}{cc}1& 4\\ 1& 5\end{array}\right]\left[\begin{array}{cc}3& 2\\ 1& 0\end{array}\right]=\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{cc}3& 2\end{array}\right]+\left[\begin{array}{c}4\\ 5\end{array}\right]\left[\begin{array}{cc}1& 0\end{array}\right]=\left[\begin{array}{cc}3& 2\\ 3& 2\end{array}\right]+\left[\begin{array}{cc}4& 0\\ 5& 0\end{array}\right]=\left[\begin{array}{cc}7& 2\\ 8& 2\end{array}\right]$$总结：通常使用行乘列求矩阵的乘积，要 $4$ 个点积（$8$ 次乘法）。列乘行得到两个完整的矩阵（同样是 $8$ 次乘法）。

【例4】（用分块消元）假设 $A$ 的第一列是 $1,3,4$，要将 $3,4$ 变成 $0,0$，需要减去主元行的 $3$ 倍和 $4$ 倍。这些行运算就是消元矩阵 $E_{21}$、$E_{32}$：$$E_{21}=\left[\begin{array}{ccc}1& 0& 0\\ -3& 1& 0\\ 0& 0& 1\end{array}\right],E_{31}=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ -4& 0& 1\end{array}\right]$$分块的思想就是用一个矩阵矩阵 $E$ 完成上面的两次消元，该矩阵将第一列的主元 $a=1$ 下面的数字全部变成 $0$：$$E=\left[\begin{array}{ccc}1& 0& 0\\ -3& 1& 0\\ -4& 0& 1\end{array}\right]乘\left[\begin{array}{ccc}1& x& x\\ 3& x& x\\ 4& x& x\end{array}\right]得到\left[\begin{array}{ccc}1& x& x\\ 0& y& y\\ 0& z& z\end{array}\right]$$使用逆矩阵，分块矩阵 $E$ 可以对整个列消元（将被消元部分看成一块）。假设矩阵有 $4$ 块 $A,B,C,D$，通过分块消去 $C$：$$分块消元\left[\begin{array}{cc}I& 0\\ -C{A}^{-1}& I\end{array}\right]\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]=\left[\begin{array}{cc}A& B\\ 0& D-C{A}^{-1}B\end{array}\right](\mathrm{2.4.6})$$消元法从第二行减去第一行 $\left[\begin{array}{cc}A& B\end{array}\right]$ 左乘 $C{A}^{-1}$（以前是 $c/a$），使得块 $C$ 变为了 $0$ 块，块 $D$ 变为 $S=D-C{A}^{-1}B$ 。
分块消元是一次处理一列，主元方块是 $A$，最后的方块是 $D-C{A}^{-1}B$，如同 $d-cb/a$，这个称为舒尔补（Schur complement）。

六、主要内容总结

1. $AB$ 的 $(i,j)$ 元素是 $(A的行i)\cdot (B的列j)$。
2. $m\times n$ 的矩阵乘 $n\times p$ 的矩阵会有 $mnp$ 次乘法。
3. $A$ 乘 $BC$ 等于 $AB$ 乘 $C$（非常重要）。
4. $AB$ 也是这 $n$ 个矩阵的和：$(A的列j)\cdot (B的行j)$。
5. 当分块矩阵的形状能正确匹配时，就可以使用分块乘法。
6. 分块消元会产生舒尔补$D-C{A}^{-1}B$。

七、例题

【例5】一个图形（或网络）有 $n$ 个节点。它的邻接矩阵（adjacency matrix）$S$ 是 $n\times n$。它是一个 $0-1$ 矩阵，当节点 $i$ 与 节点 $j$ 有边相连时 $S_{ij}=1$。

$$无向图的邻接矩阵是方阵且对称，边的两个方向均可以行走$$矩阵 $S^2$ 有一个很有用的解释，$S_{ij}^2$ 是节点 $i$ 与节点 $j$ 之间长度为 $2$ 的路径的个数。上图中节点 $2$ 与节点 $3$ 之间长度为 $2$ 的路径有两个：经过 $1$ 的路径 $2-1-3$，经过 $4$ 的路径 $2-4-3$。节点 $1$ 到节点 $1$ 长度为 $2$ 的路径也是 $2$ 个：$1-2-1$ 和 $1-3-1$。$$S^2=\left[\begin{array}{cccc}2& 1& 1& 2\\ 1& 3& 2& 1\\ 1& 2& 3& 1\\ 2& 1& 1& 2\end{array}\right],S^3=\left[\begin{array}{cccc}2& 5& 5& 2\\ 5& 4& 5& 5\\ 5& 5& 4& 5\\ 2& 5& 5& 2\end{array}\right]$$你可以找到 $5$ 条节点 $1$ 到节点 $2$ 长度为 $3$ 的路径吗？
共 $5$ 条：$1-2-1-2,1-2-3-2,1-2-4-2,1-3-1-2,1-3-4-2$。
为什么 $S^N$ 可以计算出两个节点之间长度为 $N$ 的所有路径数呢？我们从 $S^2$ 开始看某一元素的点积：$$(S^2{)}_{ij}=(S的行i)\cdot (S的列j)=S_{i1}{S}_{1j}+S_{i2}{S}_{2j}+S_{i3}{S}_{3j}+S_{i4}{S}_{4j}(\mathrm{2.4.7})$$若存在两步的路径 $i\to 1\to j$，第一个乘法得到 $S_{i1}{S}_{1j}=(1)(1)=1$，若不存在 $i\to 1\to j$ 的路径，那么要么 $i\to 1$ 不存在，要么就是 $1\to j$ 不存在，此时 $S_{i1}{S}_{1j}=0$。
$(S^2{)}_{ij}$ 会将所有的两步路径 $i\to k\to j$ 的个数累加起来，得到总路径数。同样，$S^{N-1}S$ 会计算 $N$ 步路径数，$S^{N-1}$ 表示从 $i$ 到 $k$ 的 $(N-1)$ 步的路径数，$S$ 表示从 $k$ 到 $j$ 的那一步路径数。矩阵乘法非常适合计算图形的路径，也可以看成公司内员工之间同相的频道个数。

【例6】下面有三个矩阵，什么时候 $AB=BA$ ？什么时候 $BC=CB$ ？什么时候 $A(BC)=(AB)C$ ？给出矩阵元素 $p,q,r,z$ 要满足的条件。$$A=\left[\begin{array}{cc}p& 0\\ q& r\end{array}\right],B=\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right],C=\left[\begin{array}{cc}0& z\\ 0& 0\end{array}\right]$$如果 $p,q,r,1,z$ 都是 $4\times 4$ 的块而不是数字，答案还一样吗？
解： 首先，$A(BC)=(AB)C$ 是永远正确的，该等式中括号并不需要，但是矩阵的顺序不能变。
通常情况下 $AB\ne BA$$$AB=\left[\begin{array}{cc}p& p\\ q& q+r\end{array}\right],BA=\left[\begin{array}{cc}p+q& r\\ q& r\end{array}\right]$$若要求 $AB=BA$，则需要满足 $q=0,p=r$。
$BC=CB$ 是一个巧合：$$BC=\left[\begin{array}{cc}0& z\\ 0& 0\end{array}\right],CB=\left[\begin{array}{cc}0& z\\ 0& 0\end{array}\right]$$若 $p,q,r,z$ 均是 $4\times 4$ 的块，$1$ 变为 $I$，那么所有所有的乘积也是一样的，所有答案也一样。