矩阵的乘法（线性代数及其应用【1】）

理论应用 写在前面：最近复习了一遍线性代数，想把学习成果整理出来。本系列博客主要是对学习Introduction to Linear Algebra(Fifth Edition) by Gibert Strang书籍的一个记录。

理论

矩阵定义：矩阵就是一组数的全体，通常排成长方形。下图就是一个2*2的矩阵。

$$\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$$ 矩阵乘法：对于矩阵$AB=C$有$C_{ij}$等于A矩阵的第i行的所有元素依次乘以B矩阵第j列的元素求和。 线性代数的核心工具是矩阵。而矩阵的加减法，我觉得没什么好写的，就是对应位置的元素相加减，从计算符号的角度，乘法还是有必要介绍一下的。所以，我选择从矩阵的乘法作为系列博客的第一章。

应用

邻接矩阵：用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。 例如，形如下图的连接关系图可以用矩阵表示

#mermaid-svg-RxesGIybgXu19foK .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-RxesGIybgXu19foK .label text{fill:#333}#mermaid-svg-RxesGIybgXu19foK .node rect,#mermaid-svg-RxesGIybgXu19foK .node circle,#mermaid-svg-RxesGIybgXu19foK .node ellipse,#mermaid-svg-RxesGIybgXu19foK .node polygon,#mermaid-svg-RxesGIybgXu19foK .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-RxesGIybgXu19foK .node .label{text-align:center;fill:#333}#mermaid-svg-RxesGIybgXu19foK .node.clickable{cursor:pointer}#mermaid-svg-RxesGIybgXu19foK .arrowheadPath{fill:#333}#mermaid-svg-RxesGIybgXu19foK .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-RxesGIybgXu19foK .flowchart-link{stroke:#333;fill:none}#mermaid-svg-RxesGIybgXu19foK .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-RxesGIybgXu19foK .edgeLabel rect{opacity:0.9}#mermaid-svg-RxesGIybgXu19foK .edgeLabel span{color:#333}#mermaid-svg-RxesGIybgXu19foK .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-RxesGIybgXu19foK .cluster text{fill:#333}#mermaid-svg-RxesGIybgXu19foK div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-RxesGIybgXu19foK .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-RxesGIybgXu19foK text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-RxesGIybgXu19foK .actor-line{stroke:grey}#mermaid-svg-RxesGIybgXu19foK .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-RxesGIybgXu19foK .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-RxesGIybgXu19foK #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-RxesGIybgXu19foK .sequenceNumber{fill:#fff}#mermaid-svg-RxesGIybgXu19foK #sequencenumber{fill:#333}#mermaid-svg-RxesGIybgXu19foK #crosshead path{fill:#333;stroke:#333}#mermaid-svg-RxesGIybgXu19foK .messageText{fill:#333;stroke:#333}#mermaid-svg-RxesGIybgXu19foK .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-RxesGIybgXu19foK .labelText,#mermaid-svg-RxesGIybgXu19foK .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-RxesGIybgXu19foK .loopText,#mermaid-svg-RxesGIybgXu19foK .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-RxesGIybgXu19foK .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-RxesGIybgXu19foK .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-RxesGIybgXu19foK .noteText,#mermaid-svg-RxesGIybgXu19foK .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-RxesGIybgXu19foK .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-RxesGIybgXu19foK .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-RxesGIybgXu19foK .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-RxesGIybgXu19foK .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-RxesGIybgXu19foK .section{stroke:none;opacity:0.2}#mermaid-svg-RxesGIybgXu19foK .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-RxesGIybgXu19foK .section2{fill:#fff400}#mermaid-svg-RxesGIybgXu19foK .section1,#mermaid-svg-RxesGIybgXu19foK .section3{fill:#fff;opacity:0.2}#mermaid-svg-RxesGIybgXu19foK .sectionTitle0{fill:#333}#mermaid-svg-RxesGIybgXu19foK .sectionTitle1{fill:#333}#mermaid-svg-RxesGIybgXu19foK .sectionTitle2{fill:#333}#mermaid-svg-RxesGIybgXu19foK .sectionTitle3{fill:#333}#mermaid-svg-RxesGIybgXu19foK .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-RxesGIybgXu19foK .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-RxesGIybgXu19foK .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-RxesGIybgXu19foK .grid path{stroke-width:0}#mermaid-svg-RxesGIybgXu19foK .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-RxesGIybgXu19foK .task{stroke-width:2}#mermaid-svg-RxesGIybgXu19foK .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-RxesGIybgXu19foK .taskText:not([font-size]){font-size:11px}#mermaid-svg-RxesGIybgXu19foK .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-RxesGIybgXu19foK .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-RxesGIybgXu19foK .task.clickable{cursor:pointer}#mermaid-svg-RxesGIybgXu19foK .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-RxesGIybgXu19foK .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-RxesGIybgXu19foK .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-RxesGIybgXu19foK .taskText0,#mermaid-svg-RxesGIybgXu19foK .taskText1,#mermaid-svg-RxesGIybgXu19foK .taskText2,#mermaid-svg-RxesGIybgXu19foK .taskText3{fill:#fff}#mermaid-svg-RxesGIybgXu19foK .task0,#mermaid-svg-RxesGIybgXu19foK .task1,#mermaid-svg-RxesGIybgXu19foK .task2,#mermaid-svg-RxesGIybgXu19foK .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-RxesGIybgXu19foK .taskTextOutside0,#mermaid-svg-RxesGIybgXu19foK .taskTextOutside2{fill:#000}#mermaid-svg-RxesGIybgXu19foK .taskTextOutside1,#mermaid-svg-RxesGIybgXu19foK .taskTextOutside3{fill:#000}#mermaid-svg-RxesGIybgXu19foK .active0,#mermaid-svg-RxesGIybgXu19foK .active1,#mermaid-svg-RxesGIybgXu19foK .active2,#mermaid-svg-RxesGIybgXu19foK .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-RxesGIybgXu19foK .activeText0,#mermaid-svg-RxesGIybgXu19foK .activeText1,#mermaid-svg-RxesGIybgXu19foK .activeText2,#mermaid-svg-RxesGIybgXu19foK .activeText3{fill:#000 !important}#mermaid-svg-RxesGIybgXu19foK .done0,#mermaid-svg-RxesGIybgXu19foK .done1,#mermaid-svg-RxesGIybgXu19foK .done2,#mermaid-svg-RxesGIybgXu19foK .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-RxesGIybgXu19foK .doneText0,#mermaid-svg-RxesGIybgXu19foK .doneText1,#mermaid-svg-RxesGIybgXu19foK .doneText2,#mermaid-svg-RxesGIybgXu19foK .doneText3{fill:#000 !important}#mermaid-svg-RxesGIybgXu19foK .crit0,#mermaid-svg-RxesGIybgXu19foK .crit1,#mermaid-svg-RxesGIybgXu19foK .crit2,#mermaid-svg-RxesGIybgXu19foK .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-RxesGIybgXu19foK .activeCrit0,#mermaid-svg-RxesGIybgXu19foK .activeCrit1,#mermaid-svg-RxesGIybgXu19foK .activeCrit2,#mermaid-svg-RxesGIybgXu19foK .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-RxesGIybgXu19foK .doneCrit0,#mermaid-svg-RxesGIybgXu19foK .doneCrit1,#mermaid-svg-RxesGIybgXu19foK .doneCrit2,#mermaid-svg-RxesGIybgXu19foK .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-RxesGIybgXu19foK .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-RxesGIybgXu19foK .milestoneText{font-style:italic}#mermaid-svg-RxesGIybgXu19foK .doneCritText0,#mermaid-svg-RxesGIybgXu19foK .doneCritText1,#mermaid-svg-RxesGIybgXu19foK .doneCritText2,#mermaid-svg-RxesGIybgXu19foK .doneCritText3{fill:#000 !important}#mermaid-svg-RxesGIybgXu19foK .activeCritText0,#mermaid-svg-RxesGIybgXu19foK .activeCritText1,#mermaid-svg-RxesGIybgXu19foK .activeCritText2,#mermaid-svg-RxesGIybgXu19foK .activeCritText3{fill:#000 !important}#mermaid-svg-RxesGIybgXu19foK .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-RxesGIybgXu19foK g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-RxesGIybgXu19foK g.classGroup text .title{font-weight:bolder}#mermaid-svg-RxesGIybgXu19foK g.clickable{cursor:pointer}#mermaid-svg-RxesGIybgXu19foK g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-RxesGIybgXu19foK g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-RxesGIybgXu19foK .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-RxesGIybgXu19foK .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-RxesGIybgXu19foK .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-RxesGIybgXu19foK .dashed-line{stroke-dasharray:3}#mermaid-svg-RxesGIybgXu19foK #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-RxesGIybgXu19foK #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-RxesGIybgXu19foK #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-RxesGIybgXu19foK #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-RxesGIybgXu19foK #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-RxesGIybgXu19foK #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-RxesGIybgXu19foK #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-RxesGIybgXu19foK #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-RxesGIybgXu19foK .commit-id,#mermaid-svg-RxesGIybgXu19foK .commit-msg,#mermaid-svg-RxesGIybgXu19foK .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-RxesGIybgXu19foK .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-RxesGIybgXu19foK .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-RxesGIybgXu19foK g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-RxesGIybgXu19foK g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-RxesGIybgXu19foK g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-RxesGIybgXu19foK g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-RxesGIybgXu19foK g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-RxesGIybgXu19foK g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-RxesGIybgXu19foK .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-RxesGIybgXu19foK .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-RxesGIybgXu19foK .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-RxesGIybgXu19foK .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-RxesGIybgXu19foK .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-RxesGIybgXu19foK .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-RxesGIybgXu19foK .edgeLabel text{fill:#333}#mermaid-svg-RxesGIybgXu19foK .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-RxesGIybgXu19foK .node circle.state-start{fill:black;stroke:black}#mermaid-svg-RxesGIybgXu19foK .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-RxesGIybgXu19foK #statediagram-barbEnd{fill:#9370db}#mermaid-svg-RxesGIybgXu19foK .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-RxesGIybgXu19foK .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-RxesGIybgXu19foK .statediagram-state .divider{stroke:#9370db}#mermaid-svg-RxesGIybgXu19foK .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-RxesGIybgXu19foK .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-RxesGIybgXu19foK .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-RxesGIybgXu19foK .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-RxesGIybgXu19foK .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-RxesGIybgXu19foK .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-RxesGIybgXu19foK .note-edge{stroke-dasharray:5}#mermaid-svg-RxesGIybgXu19foK .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-RxesGIybgXu19foK .error-icon{fill:#522}#mermaid-svg-RxesGIybgXu19foK .error-text{fill:#522;stroke:#522}#mermaid-svg-RxesGIybgXu19foK .edge-thickness-normal{stroke-width:2px}#mermaid-svg-RxesGIybgXu19foK .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-RxesGIybgXu19foK .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-RxesGIybgXu19foK .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-RxesGIybgXu19foK .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-RxesGIybgXu19foK .marker{fill:#333}#mermaid-svg-RxesGIybgXu19foK .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-RxesGIybgXu19foK { color: rgba(0, 0, 0, 0.75); font: ; } 节点1 节点2 节点3 节点4

用邻接矩阵表示为： $$A=\left[\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 0& 1& 1& 0\end{array}\right]$$ 其中，0表示两个点之间没有连接，比如1-1，1-4之间都是没有连接的。而1表示两个点之间是相连的比如1-2,1-3。 所以，两个邻接矩阵相乘的结果是： $$A^2=A\ast A=\left[\begin{array}{cccc}2& 1& 1& 2\\ 1& 3& 2& 1\\ 1& 2& 3& 1\\ 2& 1& 1& 2\end{array}\right]$$ 上述矩阵表示，两个点之间，用两步可以连接起来的走法有多少种。比如在矩阵$A$当中1-1之前是么有相连的。现在，矩阵$A^2$表示1-1通过两步的走法有两种，我们观察可知这两种走法分别是1-2-1,1-3-1。也就是用A矩阵的第一行，乘以A矩阵的第一列。 这里它表示是，从1-n之间的路乘以n-1的路。当有一个是断开的时候，即整个为0。只有当1-n是联通的（值为1），而n-1也是联通的时候。这时乘积才为1不为零。把所有乘积的结果进行求和，就得到了1-n-1有两条路可以走，即1-2-1,1-3-1。也就是矩阵$A^2$的第$(1,1)$个元素的值2的由来。 下面给出$A^3$矩阵，读者可以自行探索任意两点之间通过三步到达的方式的个数，以及和矩阵中的数字是否一样。 $$A^3=A\ast A\ast A=\left[\begin{array}{cccc}2& 5& 5& 2\\ 5& 4& 5& 5\\ 5& 5& 4& 5\\ 2& 5& 5& 2\end{array}\right]$$