--- title: Matrix Operations module: Matrix Algebra moduleNumber: 2 lessonNumber: 1 order: 201 summary: > Matrices add and scale entrywise, but their product is defined so that multiplication corresponds to composition of linear maps: the columns of AB are A applied to the columns of B. From that requirement follow the row-column rule, the algebra of products (associative and distributive but not commutative), powers, and the transpose. topics: [Matrix Algebra] sources: - book: Lay ref: "Ch. 2 — Matrix Algebra; §2.1 Matrix Operations" --- A [linear transformation](/linear-algebra/linear-systems/linear-transformations) $x \mapsto Ax$ is stored as a matrix; composing two such maps produces a third, and matrix multiplication is the arithmetic that computes its matrix. The single requirement $A(Bx) = (AB)x$ fixes every rule that follows: why the product is defined column by column, why it is associative but not commutative, and why its size constraints are what they are. Addition and scalar multiplication are the entrywise operations carried over from vectors. ## Notation and entries An $m \times n$ matrix $A$ has $m$ rows and $n$ columns. The scalar in row $i$ and column $j$ is the $(i,j)$-entry $a_{ij}$, and $A = [a_{ij}]$. Each column is a vector in $\mathbb{R}^m$, so writing the columns as $a_1, \dots, a_n$ gives $$ A = \begin{bmatrix} a_1 & a_2 & \cdots & a_n \end{bmatrix}, \qquad a_{ij} = (\text{$i$th entry of } a_j). $$ Several kinds of matrix recur often enough to name: - **Diagonal entries**: the entries $a_{11}, a_{22}, a_{33}, \dots$; together they form the **main diagonal**. - **Diagonal matrix**: a square matrix whose off-diagonal entries are all zero. - **Identity matrix** $I_n$: the diagonal matrix with $1$s on the diagonal, so $I_m x = x$ for every $x$ in $\mathbb{R}^m$. - **Zero matrix** $0$: every entry zero; its size is read from context. ## Sums and scalar multiples Two matrices are **equal** when they have the same size and the same corresponding entries. If $A$ and $B$ are both $m \times n$, the sum $A + B$ is the $m \times n$ matrix formed by adding corresponding entries; $A + B$ is undefined when the sizes differ. For a scalar $r$, the scalar multiple $rA$ multiplies every entry by $r$, and $-A$ means $(-1)A$, with $A - B = A + (-1)B$. > **Definition (Sum and scalar multiple).** For $m \times n$ matrices > $A = [a_{ij}]$ and $B = [b_{ij}]$ and a scalar $r$, the matrices $A + B$ and > $rA$ are the $m \times n$ matrices with entries $a_{ij} + b_{ij}$ and > $r\,a_{ij}$. Both operations act one entry at a time. For example, with $$ A = \begin{bmatrix} 4 & 0 & 5 \\ -1 & 3 & 2 \end{bmatrix}, \qquad B = \begin{bmatrix} 1 & 1 & 1 \\ 3 & 5 & 7 \end{bmatrix}, $$ we get $A + B = \begin{bmatrix} 5 & 1 & 6 \\ 2 & 8 & 9 \end{bmatrix}$ and $2B = \begin{bmatrix} 2 & 2 & 2 \\ 6 & 10 & 14 \end{bmatrix}$, so $A - 2B = \begin{bmatrix} 2 & -2 & 3 \\ -7 & -7 & -12 \end{bmatrix}$. Because addition and scaling reduce to the corresponding operations on the column vectors, matrices inherit all the familiar algebraic laws.[^lay-thm1] > **Theorem (Algebra of sums).** Let $A$, $B$, $C$ be $m \times n$ matrices and > $r$, $s$ scalars. Then $A + B = B + A$; $(A + B) + C = A + (B + C)$; > $A + 0 = A$; $r(A + B) = rA + rB$; $(r + s)A = rA + sA$; and $r(sA) = (rs)A$. ## Multiplication as composition Multiplying a vector $x$ by $B$ produces $Bx$; multiplying that in turn by $A$ produces $A(Bx)$. The composite map $x \mapsto A(Bx)$ is again linear, and the product $AB$ is defined to be its matrix, so that $$ A(Bx) = (AB)x \qquad \text{for all } x. $$ $$ % caption: The product AB is the single matrix whose action reproduces "multiply % by B, then by A" — matrix multiplication is composition of the two maps. \begin{tikzpicture}[>=stealth, font=\small, op/.style={draw, minimum width=17mm, minimum height=9mm, align=center, font=\footnotesize}] \definecolor{acc}{HTML}{4A6FA5} \node (x) at (0,0) {$x$}; \node (bx) at (3.2,0) {$Bx$}; \node (abx) at (6.6,0) {$A(Bx)$}; \draw[->, acc, thick] (x) -- (bx) node[midway, above, font=\footnotesize] {mult. by $B$}; \draw[->, acc, thick] (bx) -- (abx) node[midway, above, font=\footnotesize] {mult. by $A$}; \draw[->, black, thick] (x.south) .. controls (2.2,-1.5) and (4.4,-1.5) .. (abx.south); \node[font=\footnotesize] at (3.3,-1.35) {mult. by $AB$}; \end{tikzpicture} $$ To turn this into a formula, take $B$ with columns $b_1, \dots, b_p$ and expand $Bx = x_1 b_1 + \cdots + x_p b_p$. Linearity of multiplication by $A$ gives $$ A(Bx) = x_1(Ab_1) + \cdots + x_p(Ab_p) = \begin{bmatrix} Ab_1 & Ab_2 & \cdots & Ab_p \end{bmatrix} x. $$ The bracketed matrix is the product we set out to build. > **Definition (Matrix product).** If $A$ is $m \times n$ and $B$ is $n \times p$ > with columns $b_1, \dots, b_p$, then $AB$ is the $m \times p$ matrix > $$ > AB = A\begin{bmatrix} b_1 & \cdots & b_p \end{bmatrix} > = \begin{bmatrix} Ab_1 & \cdots & Ab_p \end{bmatrix}. > $$ > Each column of $AB$ is a linear combination of the columns of $A$ using the > corresponding column of $B$ as weights. Two consequences of the definition: - The number of columns of $A$ must equal the number of rows of $B$ (the "inner" dimensions match), or $Ab_j$ is undefined. - $AB$ has as many rows as $A$ and as many columns as $B$ (the "outer" dimensions). $$ % caption: Size bookkeeping for AB: the inner dimensions must agree, and the % outer dimensions become the size of the product. \begin{tikzpicture}[font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} \node (a) at (0,0) {$A$}; \node (b) at (2.4,0) {$B$}; \node[anchor=west] (eq) at (4.4,0) {$AB$}; \node[below=1pt of a, font=\scriptsize, text=black] {$m$-by-$n$}; \node[below=1pt of b, font=\scriptsize, text=black] {$n$-by-$p$}; \node[below=1pt of eq, font=\scriptsize, text=black] {$m$-by-$p$}; \draw[acc, thick, ->] (-0.35,-0.75) .. controls (0.6,-1.4) and (1.8,-1.4) .. (2.75,-0.75); \node[acc, font=\scriptsize] at (1.2,-1.5) {inner $n$ must match}; \draw[black, thick] (0.3,0.55) -- (2.05,0.55); \node[black, font=\scriptsize] at (1.2,0.8) {outer $m,\,p$ survive}; \end{tikzpicture} $$ For example, if $A$ is $3 \times 5$ and $B$ is $5 \times 2$, then $AB$ is $3 \times 2$, while $BA$ is undefined because the $2$ columns of $B$ do not match the $3$ rows of $A$. ### The row-column rule The column definition is right for theory, but individual entries are computed faster by pairing a row of $A$ with a column of $B$. > **Theorem (Row-column rule).** If the product $AB$ is defined and $A$ is > $m \times n$, then the $(i,j)$-entry of $AB$ is > $$ > (AB)_{ij} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj} > = \sum_{k=1}^{n} a_{ik}b_{kj}. > $$ The entry in position $(i,j)$ is the dot product of row $i$ of $A$ with column $j$ of $B$. A related identity records what a whole row of the product is: $\operatorname{row}_i(AB) = \operatorname{row}_i(A)\, B$. $$ % caption: The (i,j)-entry of AB pairs the ith row of A with the jth column of % B and sums the products of matched entries. \begin{tikzpicture}[font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} % matrix A \draw[black] (0,0) rectangle (2.4,1.8); \node[font=\scriptsize, text=black] at (1.2,2.05) {$A$}; \fill[acc!14] (0,1.2) rectangle (2.4,1.8); \draw[acc, thick] (0,1.2) rectangle (2.4,1.8); \node[acc, font=\scriptsize] at (-0.45,1.5) {row $i$}; % matrix B \draw[black] (3.6,-0.6) rectangle (5.4,1.8); \node[font=\scriptsize, text=black] at (4.5,2.05) {$B$}; \fill[acc!14] (4.2,-0.6) rectangle (4.8,1.8); \draw[acc, thick] (4.2,-0.6) rectangle (4.8,1.8); \node[acc, font=\scriptsize] at (4.5,-0.9) {col $j$}; % product \draw[black] (6.8,0) rectangle (9.0,1.8); \node[font=\scriptsize, text=black] at (7.9,2.05) {$AB$}; \fill[acc!30] (7.55,1.2) rectangle (8.15,1.8); \draw[acc, thick] (7.55,1.2) rectangle (8.15,1.8); \node[acc, font=\scriptsize] at (7.85,0.55) {entry $(i,j)$}; \draw[->, black, thick] (2.55,1.5) .. controls (3.1,1.5) .. (3.5,1.5); \draw[->, black, thick] (4.5,-0.75) .. controls (4.5,-1.1) and (7.85,-1.1) .. (7.85,-0.05); \draw[->, acc, thick] (6.9,1.5) -- (7.5,1.5); \end{tikzpicture} $$ > **Worked example.** Multiply > $A = \begin{bmatrix} 2 & 3 \\ 1 & -5 \end{bmatrix}$ and > $B = \begin{bmatrix} 4 & 3 & 6 \\ 1 & -2 & 3 \end{bmatrix}$. Here $A$ is > $2 \times 2$ and $B$ is $2 \times 3$, so $AB$ is $2 \times 3$. Each entry pairs > a row of $A$ with a column of $B$: > > $$ > (AB)_{11} = 2\cdot 4 + 3\cdot 1 = 11, \quad > (AB)_{12} = 2\cdot 3 + 3(-2) = 0, \quad > (AB)_{13} = 2\cdot 6 + 3\cdot 3 = 21, > $$ > > $$ > (AB)_{21} = 1\cdot 4 + (-5)\cdot 1 = -1, \quad > (AB)_{22} = 1\cdot 3 + (-5)(-2) = 13, \quad > (AB)_{23} = 1\cdot 6 + (-5)\cdot 3 = -9. > $$ > > Assembling the entries, > > $$ > AB = \begin{bmatrix} 11 & 0 & 21 \\ -1 & 13 & -9 \end{bmatrix}. > $$ > > The first column $(11, -1)$ is also > $4\begin{bmatrix}2\\1\end{bmatrix} + 1\begin{bmatrix}3\\-5\end{bmatrix}$, the > columns of $A$ weighted by column $1$ of $B$: the column definition and the > row-column rule agree. ## The algebra of products Because matrix multiplication is composition of functions, and composition of functions is associative, products obey the same grouping and distribution rules as ordinary arithmetic, with one omission: commutativity.[^lay-thm2] > **Theorem (Algebra of products).** Let $A$ be $m \times n$, and let $B$, $C$ > have sizes for which the sums and products below are defined, with $r$ a scalar. > Then > $$ > A(BC) = (AB)C, \qquad A(B + C) = AB + AC, \qquad (B + C)A = BA + CA, > $$ > $$ > r(AB) = (rA)B = A(rB), \qquad I_m A = A = A I_n. > $$ Associativity lets parentheses move freely, so a product $ABCD$ is unambiguous as long as the left-to-right order is preserved. That order is where matrix algebra departs from scalar algebra. > **Warning (Three failures).** Matrix multiplication is not the arithmetic of > real numbers. In general: > > - $AB \ne BA$ — the factors rarely commute. > - Cancellation fails: $AB = AC$ does not force $B = C$. > - $AB = 0$ does not force $A = 0$ or $B = 0$. Non-commutativity is visible in the columns: the columns of $AB$ are combinations of the columns of $A$, whereas the columns of $BA$ are built from the columns of $B$, so the two products describe different maps. When $AB = BA$ does hold, $A$ and $B$ are said to **commute**. > **Worked example.** Matrix products rarely commute. With > $A = \begin{bmatrix} 5 & 1 \\ 3 & -2 \end{bmatrix}$ and > $B = \begin{bmatrix} 2 & 0 \\ 4 & 3 \end{bmatrix}$, > > $$ > AB = \begin{bmatrix} 5\cdot 2 + 1\cdot 4 & 5\cdot 0 + 1\cdot 3 \\ 3\cdot 2 + (-2)\cdot 4 & 3\cdot 0 + (-2)\cdot 3 \end{bmatrix} > = \begin{bmatrix} 14 & 3 \\ -2 & -6 \end{bmatrix}, > $$ > > $$ > BA = \begin{bmatrix} 2\cdot 5 + 0\cdot 3 & 2\cdot 1 + 0(-2) \\ 4\cdot 5 + 3\cdot 3 & 4\cdot 1 + 3(-2) \end{bmatrix} > = \begin{bmatrix} 10 & 2 \\ 29 & -2 \end{bmatrix}. > $$ > > The two products disagree in every entry, so $AB \ne BA$. ### Powers For a square $n \times n$ matrix $A$ and a positive integer $k$, the power $A^k$ is the product of $k$ copies of $A$: $$ A^k = \underbrace{A A \cdots A}_{k}, \qquad A^0 = I. $$ Setting $A^0 = I$ keeps $A^k x$ meaning "apply $A$ to $x$ a total of $k$ times," with zero applications leaving $x$ unchanged. Powers of matrices drive the [Leontief model](/linear-algebra/matrix-algebra/applications-leontief-and-graphics), Markov chains, and the study of [eigenvalues](/linear-algebra/eigenvalues/eigenvectors-and-eigenvalues), where a good factorization of $A$ turns $A^k$ into something computable. ## The transpose Rows and columns exchange roles under the transpose. > **Definition (Transpose).** The transpose of an $m \times n$ matrix $A$ is the > $n \times m$ matrix $A^\top$ whose $(i,j)$-entry is $a_{ji}$: column $i$ of > $A^\top$ is row $i$ of $A$. Equivalently, $A^\top$ is $A$ reflected across its > main diagonal. $$ % caption: The transpose reflects a matrix across its main diagonal; the (i,j) % entry lands in position (j,i). \begin{tikzpicture}[font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} % A \node[font=\scriptsize, text=black] at (0.9,2.15) {$A$}; \draw[black, step=0.6] (0,0) grid (1.8,1.8); \draw[black, thick] (0,0) rectangle (1.8,1.8); \node at (0.3,1.5) {$a$}; \node at (0.9,1.5) {$b$}; \node at (1.5,1.5) {$c$}; \node at (0.3,0.9) {$d$}; \node at (0.9,0.9) {$e$}; \node at (1.5,0.9) {$f$}; \node at (0.3,0.3) {$g$}; \node at (0.9,0.3) {$h$}; \node at (1.5,0.3) {$i$}; \draw[acc, thick, dashed] (0,1.8) -- (1.8,0); % arrow \draw[->, acc, very thick] (2.4,0.9) -- (3.6,0.9) node[midway, above, font=\scriptsize] {transpose}; % A^T \begin{scope}[xshift=4.2cm] \node[font=\scriptsize, text=black] at (0.9,2.15) {$A^{T}$}; \draw[black, step=0.6] (0,0) grid (1.8,1.8); \draw[black, thick] (0,0) rectangle (1.8,1.8); \node at (0.3,1.5) {$a$}; \node at (0.9,1.5) {$d$}; \node at (1.5,1.5) {$g$}; \node at (0.3,0.9) {$b$}; \node at (0.9,0.9) {$e$}; \node at (1.5,0.9) {$h$}; \node at (0.3,0.3) {$c$}; \node at (0.9,0.3) {$f$}; \node at (1.5,0.3) {$i$}; \draw[acc, thick, dashed] (0,1.8) -- (1.8,0); \end{scope} \end{tikzpicture} $$ The transpose interacts with the other operations through four rules; the last reverses the order of a product.[^lay-thm3] > **Theorem (Transpose rules).** For matrices of compatible sizes and a scalar > $r$: > $$ > (A^\top)^\top = A, \quad (A + B)^\top = A^\top + B^\top, \quad > (rA)^\top = rA^\top, \quad (AB)^\top = B^\top A^\top. > $$ In words, the transpose of a product is the product of the transposes in reverse order, and this extends to any number of factors: $(ABC)^\top = C^\top B^\top A^\top$. In general $(AB)^\top \ne A^\top B^\top$, even when the right side happens to be defined. ### Inner and outer products Viewing a vector in $\mathbb{R}^n$ as an $n \times 1$ matrix turns two special transpose products into familiar objects. For $u, v \in \mathbb{R}^n$: - **Inner product** $u^\top v$: a $1 \times 1$ matrix, written as the single real number $u_1 v_1 + \cdots + u_n v_n$. This is the dot product that underlies [length and orthogonality](/linear-algebra/orthogonality-least-squares/inner-product-length-orthogonality). - **Outer product** $u v^\top$: an $n \times n$ matrix whose $(i,j)$-entry is $u_i v_j$. Outer products reappear as the rank-one pieces of [block multiplication](/linear-algebra/matrix-algebra/partitioned-matrices-and-lu) and the SVD. | Operation | Requirement | Result size | Reads as | | --- | --- | --- | --- | | $A + B$ | same size | $m \times n$ | entrywise sum | | $rA$ | any | $m \times n$ | entrywise scale | | $AB$ | cols $A$ = rows $B$ | $m \times p$ | composition of maps | | $A^\top$ | any | $n \times m$ | reflect across diagonal | | $u^\top v$ | same length | $1 \times 1$ | scalar (dot product) | | $u v^\top$ | any lengths | $n \times m$ | rank-one matrix | ## Numerical note High-performance libraries such as LAPACK compute $AB$ one column at a time, in agreement with the column definition, because that layout matches how matrices are stored in memory and because the columns of $AB$ can be assigned to separate processors and computed in parallel. The order of a chained product also matters for cost, not just correctness: when $B$ is square and $C$ has few columns, computing $A(BC)$ can be far cheaper than $(AB)C$, even though the two agree by associativity. The [LU factorization](/linear-algebra/matrix-algebra/partitioned-matrices-and-lu) turns these observations into a systematic way to solve many systems at once. [^lay-thm1]: **Lay**, _Linear Algebra and Its Applications_, §2.1 — Theorem 1: the commutative, associative, and distributive laws for matrix sums and scalar multiples, each verified column by column from the vector case. [^lay-thm2]: **Lay**, §2.1 — Theorem 2: associativity of multiplication follows from associativity of function composition, together with the two distributive laws, $r(AB) = (rA)B = A(rB)$, and $I_m A = A = A I_n$; the accompanying warnings collect the three ways matrix algebra differs from scalar algebra. [^lay-thm3]: **Lay**, §2.1 — Theorem 3 and the definition of the transpose, including $(AB)^\top = B^\top A^\top$ and the inner/outer product interpretations of $u^\top v$ and $u v^\top$.