Matrix methods and simultaneous models

Matrix products describe how quantities are combined; row operations then solve simultaneous balances, before we examine applications and practice.

Here a linear map preserves vector addition and multiplication by real scalars, so it sends the zero vector to zero; see linear-map preparation.

Matrix notation and products

Definition

When a matrix product is defined

If $A$ is an $m \times n$ matrix and $B$ is an $n \times p$ matrix, then the product $AB$ is defined and is an $m \times p$ matrix.

If the number of columns of $A$ does not equal the number of rows of $B$, then the product $AB$ is undefined.

Definition

Matrix multiplication

Suppose $A = [a_{ij}]$ is an $m \times n$ matrix and $B = [b_{jk}]$ is an $n \times p$ matrix.

Then the $(i,k)$ entry of $AB$ is

$$(AB)_{ik} = a_{i1}b_{1k} + a_{i2}b_{2k} + \cdots + a_{in}b_{nk}.$$

So each output entry is the dot-product-style combination of row $i$ of $A$ with column $k$ of $B$.

Identity matrices do nothing, on purpose

Definition

Identity matrix

For each positive integer $n$, the identity matrix $I_n$ is the $n \times n$ square matrix with $1$ on the main diagonal and $0$ everywhere else.

For example,

$$I_2 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \qquad I_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}.$$

The identity matrix matters because it preserves any compatible matrix:

$$AI_n = A, \qquad I_m A = A$$

whenever the sizes match.

Worked example

Why multiplying by the identity changes nothing

Let

$$A = \begin{bmatrix} 2 & -1 \\ 4 & 3 \end{bmatrix}.$$

Then

$$AI_2 = \begin{bmatrix} 2 & -1 \\ 4 & 3 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 2 & -1 \\ 4 & 3 \end{bmatrix}.$$

The first column of $AI_2$ reproduces the first column of $A$, and the second column reproduces the second column of $A$.

Counterexample mode

Matching dimensions do not guarantee commutativity

The claim “two square matrices of the same size always satisfy $AB=BA$” is false even though both products exist and have the same size. Take

$$A=\begin{bmatrix}1&2\\3&4\end{bmatrix},\qquad B=\begin{bmatrix}0&0\\0&1\end{bmatrix}.$$

Both are real $2\times2$ matrices, so the hypothesis is satisfied. Direct row-by-column multiplication gives

$$AB=\begin{bmatrix}0&2\\0&4\end{bmatrix},\qquad BA=\begin{bmatrix}0&0\\3&4\end{bmatrix}.$$

For example, $(AB)_{12}=1\cdot0+2\cdot1=2$, whereas $(BA)_{12}=0\cdot2+0\cdot4=0$. One unequal corresponding entry is enough to prove $AB\ne BA$. The failure has a structural explanation: multiplying this $B$ on the right keeps the second column and zeros the first, while multiplying it on the left keeps the second row and zeros the first.

A valid replacement is: a square matrix commutes with every scalar multiple of the identity of the same size. Indeed, if $B=cI$, then $AB=A(cI)=cA=(cI)A=BA$. For arbitrary square matrices, commutativity needs its own justification; matching dimensions guarantees that multiplication is defined, not that factors can be interchanged.

Matrix multiplication represents composition

The multiplication rule is not arbitrary. It is the rule that makes matrices encode linear transformations in sequence.

If a vector $x$ is first sent to $Bx$, and then that result is sent to $A(Bx)$, the combined effect is

$$(AB)x.$$

That is why the inner dimensions must match. The output of the first map must be a valid input for the second one.

Theorem

Associativity matches repeated composition

Whenever the products are defined,

$$A(BC) = (AB)C.$$

So we may regroup a chain of matrix products without changing the final linear transformation.

This does not mean that order may be changed. Associativity lets us change parentheses, not the order of the factors themselves.

Definition

Transpose

If $A = [a_{ij}]$ is an $m \times n$ matrix, then its transpose $A^T$ is the $n \times m$ matrix whose $(j,i)$ entry is $a_{ij}$.

Equivalently,

$$(A^T)_{ji} = a_{ij}.$$

So every row of $A$ becomes a column of $A^T$, and every column of $A$ becomes a row.

Theorem

Basic properties of transpose

Let $A$ and $B$ have the same size when they are added, let $c$ be a scalar, and suppose $A$ is $m \times n$ and $B$ is $n \times p$ when they are multiplied. Then:

1. $(A^T)^T = A$
2. $(A + B)^T = A^T + B^T$
3. $(cA)^T = cA^T$
4. $(AB)^T = B^T A^T$

Proof

Entrywise proof of the product rule

Let $A=[a_{ij}]$ be $m \times n$ and $B=[b_{ij}]$ be $n \times p$. Then $AB$ is $m \times p$, so both $(AB)^T$ and $B^T A^T$ are $p \times m$. For $1 \le i \le p$ and $1 \le j \le m$, the $(i,j)$ entry of the first matrix is

$$\bigl((AB)^T\bigr)_{ij} =(AB)_{ji} =\sum_{k=1}^{n} a_{jk}b_{ki}.$$

On the other hand, the $(i,j)$ entry of $B^T A^T$ is

$$\begin{aligned} (B^T A^T)_{ij} &=\sum_{k=1}^{n}(B^T)_{ik}(A^T)_{kj} \\ &=\sum_{k=1}^{n}b_{ki}a_{jk} \\ &=\sum_{k=1}^{n}a_{jk}b_{ki}. \end{aligned}$$

The last equality uses commutativity of scalar multiplication, not commutativity of matrix multiplication. Corresponding entries therefore agree, so $(AB)^T=B^T A^T$. The dimensions also explain the reversed order: $B^T$ is $p \times n$ and $A^T$ is $n \times m$, whereas $A^T B^T$ would generally not even be defined.

Compatible matrix identities and linearity

Work with real matrices of positive finite sizes. Addition and scalar multiplication are entrywise. A map is linear if $L(\alpha x+\beta y)=\alpha L(x)+\beta L(y)$ for all inputs and real scalars. The row-column formula proves $x\mapsto Ax$ is linear by distributing each finite scalar sum; taking $x=y=0$ gives $L(0)=0$. For $A$ of size $m\times n$, $B$ of size $n\times p$ and $C$ of size $p\times q$,

$$((AB)C)_{i\ell}=\sum_{k=1}^p\sum_{j=1}^n a_{ij}b_{jk}c_{k\ell}=\sum_{j=1}^n a_{ij}\sum_{k=1}^p b_{jk}c_{k\ell}=(A(BC))_{i\ell}.$$

Only finite sums were regrouped. The same entrywise distributive law proves matrix distributivity, and the Kronecker entries of $I$ prove $AI=A=IA$ in compatible sizes. The definition of transpose directly gives $(A^T)^T=A$, $(A+B)^T=A^T+B^T$, and $(cA)^T=cA^T$. If $\Delta=ad-bc\ne0$, multiplying $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ and $\begin{pmatrix}d&-b\\-c&a\end{pmatrix}$ in either order gives $\Delta I_2$; division by $\Delta$ proves the stated two-by-two inverse formula.

Definition

Standard inner product

Let $u$ and $v$ be column vectors in $\mathbb{R}^m$, with the same dimension $m\ge1$. Their inner product is the real number

$$\langle u,v\rangle =\sum_{i=1}^m u_iv_i =u^Tv.$$

It is also called the dot product. We deliberately identify a $1\times1$ matrix with its single real entry, so the matrix product $u^Tv$ is read as a number.

Linear systems and their solution sets

Definition

Coefficient matrix, constant vector, and augmented matrix

For a system $Ax = b$:

• $A$ is the coefficient matrix;
• $b$ is the vector of constants;
• $[A\mid b]$ is the augmented matrix, formed by placing the constant column beside the coefficient matrix.

The vertical bar is bookkeeping. It reminds you which column came from the right-hand side, but it does not create a new kind of matrix operation.

Definition

Elementary row operations

The allowed operations on an augmented matrix are:

1. $R_i \leftrightarrow R_j$, where $i\ne j$
2. $R_i \leftarrow \alpha R_i$, where $\alpha \ne 0$
3. $R_j \leftarrow \alpha R_i+R_j$, where $i\ne j$ and $\alpha\in\mathbb R$

These are called elementary row operations.

Theorem

Row-equivalent augmented matrices represent equivalent systems

If one augmented matrix is obtained from another by a sequence of elementary row operations, then the two corresponding systems are equivalent: they have exactly the same solution set.

Proof

Why each elementary row operation is safe

Each operation is just an equation operation written in matrix form.

• Swapping two rows only changes the order in which the equations are listed. A number tuple solves all equations before the swap if and only if it solves all equations after the swap.
• Multiplying a row by a nonzero scalar multiplies both sides of one equation by the same nonzero number. That produces an equivalent equation, and the move is reversible by multiplying by $1 / \alpha$.
• Replacing $R_j$ by $\alpha R_i + R_j$ means replacing equation $j$ by “$\alpha \times$ equation $i$ plus equation $j$.” Any solution of the original system still satisfies the new equation, and the move is reversible by adding $-\alpha$ times row $i$ back to row $j$.

So every elementary row operation preserves the solution set, and therefore any finite sequence of them does the same.

Definition

REF and RREF

A matrix is in row echelon form (REF) when:

1. all zero rows are at the bottom, and
2. each nonzero row starts farther to the right than the row above it.

A matrix is in reduced row echelon form (RREF) when, in addition:

1. each pivot is $1$, and
2. each pivot is the only nonzero entry in its column.

One full elimination path

Consider the system

$$\begin{aligned} x + 2y + 2z &= 4, \\ x + 3y + 3z &= 5, \\ 2x + 6y + 5z &= 6. \end{aligned}$$

Its augmented matrix is

$$\begin{bmatrix} 1 & 2 & 2 & 4 \\ 1 & 3 & 3 & 5 \\ 2 & 6 & 5 & 6 \end{bmatrix}.$$

Worked example

Read every row operation as a purpose

The entry in the top-left corner is already a convenient pivot because it is $1$. So the first goal is simple:

make everything below that pivot become $0$.

Use

$$R_2 \leftarrow R_2 - R_1, \qquad R_3 \leftarrow R_3 - 2R_1.$$

Then the matrix becomes

$$\begin{bmatrix} 1 & 2 & 2 & 4 \\ 0 & 1 & 1 & 1 \\ 0 & 2 & 1 & -2 \end{bmatrix}.$$

Now column 1 is finished. The next pivot lives in row 2, column 2. So we use it to clear the $2$ below it:

$$R_3 \leftarrow R_3 - 2R_2.$$

This gives

$$\begin{bmatrix} 1 & 2 & 2 & 4 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & -1 & -4 \end{bmatrix}.$$

This matrix is in REF. Read the equations from bottom to top:

$$-z=-4\ \Longrightarrow\ z=4,\qquad y+z=1\ \Longrightarrow\ y=-3,\qquad x+2y+2z=4\ \Longrightarrow\ x=2.$$

The system is already solved. Continuing to RREF records these substitutions in the matrix itself, so that each variable's value can be read directly.

First make the last pivot equal to $1$:

$$R_3 \leftarrow -R_3 \quad\Rightarrow\quad \begin{bmatrix} 1 & 2 & 2 & 4 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 4 \end{bmatrix}.$$

Then clear the entries above that pivot:

$$R_1 \leftarrow R_1 - 2R_3, \qquad R_2 \leftarrow R_2 - R_3,$$

so the matrix becomes

$$\begin{bmatrix} 1 & 2 & 0 & -4 \\ 0 & 1 & 0 & -3 \\ 0 & 0 & 1 & 4 \end{bmatrix}.$$

Finally clear the $2$ above the second pivot:

$$R_1 \leftarrow R_1 - 2R_2,$$

which gives the RREF

$$\begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & -3 \\ 0 & 0 & 1 & 4 \end{bmatrix}.$$

Now the solution can be read immediately:

$$x = 2,\qquad y = -3,\qquad z = 4.$$

Worked example

Read structure before you compute

Suppose you arrive at

$$\begin{bmatrix} 1 & 0 & 3 & 5 \\ 0 & 1 & -2 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

Here columns 1 and 2 are pivot columns, but column 3 is not. That means the third variable is free.

So this system does not have one unique solution. Instead, it has infinitely many solutions, because you may choose the free variable first and then solve for the pivot variables.

Theorem

What a contradiction row means

If row reduction produces a row such as

$$\begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix},$$

then the corresponding equation is $0 = 1$. That is impossible, so the system is inconsistent and has no solution.

Definition

Homogeneous system

A homogeneous linear system is a linear system of the form

$$Ax = 0.$$

Its trivial solution is the zero vector $x = 0$.

Definition

Null space

For a real $m\times n$ matrix $A$, the null space of $A$ is

$$N(A) = \{x\in\mathbb R^n : Ax = 0_m\}.$$

So $N(A)$ is exactly the solution set of the homogeneous system $Ax = 0$.

Theorem

Every solution is a particular solution plus a null-space vector

Suppose $x_p$ is one particular solution of $Ax = b$.

Then a vector $x$ solves $Ax = b$ if and only if

$$x = x_p + v$$

for some $v \in N(A)$.

Proof

Why the full solution set has the form $x_p + N(A)$

First suppose $x$ is any solution of $Ax = b$. Then

$$Ax = b \qquad \text{and} \qquad Ax_p = b.$$

Subtracting gives

$$A(x - x_p) = 0.$$

So $x - x_p \in N(A)$, which means $x = x_p + v$ for some $v \in N(A)$.

Conversely, if $v \in N(A)$, then $Av = 0$. Hence

$$A(x_p + v) = Ax_p + Av = b + 0 = b.$$

So every vector of the form $x_p + v$ is also a solution.

Real square inverses and the two-by-two formula

Definition

Invertible matrix

Let $A$ be a $p \times p$ square matrix. We say that $A$ is invertible if there exists a $p \times p$ matrix $B$ such that

$$BA = AB = I_p.$$

The matrix $B$ is called the inverse of $A$, and we write $B = A^{-1}$.

Theorem

The inverse is unique

Let $A$ be $p\times q$ and let $B,C$ be $q\times p$. If $B$ is a left inverse of $A$ and $C$ is a right inverse, then $B=C$. In particular, an invertible square matrix has exactly one inverse.

Proof

Why the inverse is unique

The assumptions are $BA=I_q$ and $AC=I_p$. Associativity gives

$$B=BI_p=B(AC)=(BA)C=I_qC=C.$$

No factors were interchanged. For an invertible square matrix, any two inverses satisfy these hypotheses, so they coincide.

Let

$$A= \begin{bmatrix} a&b\\ c&d \end{bmatrix}, \qquad \det(A)=ad-bc\neq0.$$ $$A^{-1}= \frac{1}{ad-bc} \begin{bmatrix} d&-b\\ -c&a \end{bmatrix}.$$

The uniqueness proof is in invertible matrices.

Real square determinants and invertibility

The following statements concern finite real square matrices; the first statement additionally requires the matrix to be upper or lower triangular.

Theorem

Triangular determinant theorem

If $T$ is upper triangular or lower triangular, then

$$\det(T)=t_{11}t_{22}\cdots t_{nn}.$$

Theorem

Determinant criterion for invertibility

For a square matrix $A$,

$$A\text{ is invertible}\quad\Longleftrightarrow\quad\det(A)\ne0.$$

Build the determinant from smaller matrices

Definition

Submatrix, minor, and cofactor

Let $A=[a_{ij}]$ be an $n\times n$ matrix with $n\ge 2$. For indices $1\le i,j\le n$, delete row $i$ and column $j$ simultaneously. The resulting $(n-1)\times(n-1)$ matrix is the submatrix $A(i\mid j)$.

The minor belonging to $a_{ij}$ is the scalar

$$M_{ij}=\det\bigl(A(i\mid j)\bigr).$$

The cofactor belonging to $a_{ij}$ is the signed scalar

$$C_{ij}=(-1)^{i+j}M_{ij}.$$

The signs form a checkerboard whose upper-left sign is positive:

$$\begin{bmatrix} +&-&+&\cdots\\ -&+&-&\cdots\\ +&-&+&\cdots\\ \vdots&\vdots&\vdots&\ddots \end{bmatrix}.$$

The notation $A(i\mid j)$ names a matrix, $M_{ij}$ is a determinant of that matrix, and $C_{ij}$ is that scalar after the sign has been attached. Keeping these three objects distinct prevents a common double-sign error.

Definition

Recursive definition of the determinant

For a $1\times1$ matrix $[a_{11}]$, define

$$\det([a_{11}])=a_{11}.$$

For an $n\times n$ matrix with $n>1$, define its determinant by expansion along the first row:

$$\det(A)=\sum_{j=1}^{n}a_{1j}C_{1j} =\sum_{j=1}^{n}(-1)^{1+j}a_{1j}M_{1j}.$$

This is a definition, not yet a theorem about other rows or columns. Each minor in the sum has size $n-1$, so repeated use of the definition eventually reaches the $1\times1$ base case. No $0\times0$ determinant convention is needed: the submatrix and minor definitions are used only for $n\ge2$.

Follow cofactor expansion turn one determinant into smaller signed branches, then see how zeros prune the tree and triangular matrices collapse to diagonal products.

1. Minor, sign, cofactor

   Delete row i and column j and take the remaining determinant to obtain the minor. Multiplying that scalar by (-1)^{i+j} gives the cofactor.

2. Expansion branches

   For B=[[3,2,-1],[4,1,6],[-3,-1,2]], expansion along the first row has coefficients 3, -2, and -1 multiplying the three minors.

3. Combine branch values

   The three minors are 8, 26, and -1. Including the entries and checkerboard signs gives 3(8)-2(26)+(-1)(-1)=-27.

4. Zeros prune work

   A zero entry contributes a zero cofactor term, so choosing a sparse row or column removes branches immediately.

5. One nonzero entry

   If a row or column has only one nonzero entry, the determinant collapses to one signed smaller determinant.

6. Triangular read-off

   For a triangular matrix, repeated one-branch expansion leaves the product of the diagonal entries.

Cofactor expansion is both a recursive definition and a computation strategy: choose sparse rows or columns so zero branches disappear before they cost work.

Arbitrary cofactor expansion from the recursive determinant

Let $A$ be real $n\times n$, $n\ge1$, with determinant defined by the one-by-one base case and first-row recursion. Let $S_n$ be the permutations of $1,\ldots,n$. Define the inversion number $\operatorname{inv}(\sigma)$ as the number of pairs $r<s$ with $\sigma(r)>\sigma(s)$, and put $\operatorname{sgn}(\sigma)=(-1)^{\operatorname{inv}(\sigma)}$.

Suppose $\sigma(i)=j$ and delete position $i$ and value $j$, keeping the relative orders of the remaining positions and values; the resulting permutation is $\tau\in S_{n-1}$. If $u$ entries before position $i$ are smaller than $j$, the inversions removed are $(i-1-u)+(j-1-u)=i+j-2-2u$. Consequently

$$\operatorname{sgn}(\sigma)=(-1)^{i+j}\operatorname{sgn}(\tau).$$

Define $P_n(A)=\sum_{\sigma\in S_n}\operatorname{sgn}(\sigma)\prod_{r=1}^n a_{r,\sigma(r)}$. For $n=1$, it is the recursive determinant. For $n>1$, grouping by $\sigma(1)=j$ and using the sign identity gives $P_n(A)=\sum_j(-1)^{1+j}a_{1j}P_{n-1}(A(1\mid j))$. Induction therefore proves $P_n(A)=\det A$.

Now fix any row $i$ and group the same finite permutation sum by $\sigma(i)=j$. Deletion is a bijection to all permutations of the corresponding minor, so

$$\det A=\sum_{j=1}^n(-1)^{i+j}a_{ij}\det(A(i\mid j)).$$

For a fixed column $j$, each permutation has a unique position $i$ with $\sigma(i)=j$. Grouping by that position gives

$$\det A=\sum_{i=1}^n(-1)^{i+j}a_{ij}\det(A(i\mid j)).$$

Both expansion formulas concern $n\ge2$, so no empty determinant convention was introduced. This proves the general expansion theorem without assuming alternating row rules or the determinant product theorem.

Why the structural rules follow

Zero rows and zero columns

Theorem

A zero row or zero column gives determinant zero

If every entry in one row or one column of a square matrix is zero, then its determinant is zero.

Theorem

A row or column with one possible nonzero entry

For a square matrix of size $n\ge2$, suppose all entries in row $k$ are zero except possibly $c_{k\ell}$. Then

$$\det(C)=c_{k\ell}(-1)^{k+\ell}\det\bigl(C(k\mid\ell)\bigr).$$

The same formula holds when all entries in column $\ell$ are zero except possibly $c_{k\ell}$. The formula includes the case $c_{k\ell}=0$.

For $n=1$, a matrix with a zero row is $[0]$, whose determinant is $0$ by the base definition. For $n\ge2$, expand along that row using the arbitrary-row theorem. Every term has a zero entry as its factor, so every term is zero and hence $\det(A)=0$.

The zero-column statement can be proved directly by induction, which makes the inheritance of the zero column explicit. For $n=1$, the only $1\times1$ matrix with a zero column is $[0]$, and its determinant is $0$. Assume the statement for $n=k$. Let $C$ be a $(k+1)\times(k+1)$ matrix with zero column $\ell$. Expand along the first row. The term from column $\ell$ is zero. In every other term, delete row $1$ and a column $j\ne\ell$; the original zero column survives as a zero column of the resulting $k\times k$ submatrix (with its index shifted when $j\lt\ell$). By the induction hypothesis each such submatrix has determinant zero. Hence every term is zero, proving $\det(C)=0$.

For the one-support theorem, the row case follows by expanding along row $k$: all terms except the $\ell$-term vanish. For the column case, expand along row $k$. The $\ell$-term remains. For each $j\ne\ell$, the submatrix $C(k\mid j)$ inherits a zero column from column $\ell$ of $C$, so its determinant is zero by the zero-column result. Therefore only $c_{k\ell}(-1)^{k+\ell}\det(C(k\mid\ell))$ remains. This is the precise reason that a sparse row or column collapses the calculation to one minor.

Triangular matrices

Theorem

Triangular determinant theorem

If $T$ is upper triangular or lower triangular, then

$$\det(T)=t_{11}t_{22}\cdots t_{nn}.$$

We prove the upper-triangular statement by induction on $n$. For $n=1$, it is the determinant definition. Suppose it holds for upper-triangular $k\times k$ matrices, and let $T$ be upper triangular of size $k+1$. Its last row has zero entries except possibly $t_{k+1,k+1}$. Expanding along that last row gives

$$\det(T)=t_{k+1,k+1}\det\bigl(T(k+1\mid k+1)\bigr),$$

because the sign is $(-1)^{2k+2}=1$. The retained submatrix is still upper triangular, with diagonal $t_{11},\ldots,t_{kk}$. By induction its determinant is $t_{11}\cdots t_{kk}$, giving the required product through $t_{k+1,k+1}$. For a lower-triangular matrix, expand along the first row, whose only possible nonzero entry is $t_{11}$; the retained submatrix is lower triangular with diagonal $t_{22},\ldots,t_{nn}$, and the same induction proves the result.

Multilinearity in one fixed row

Theorem

Multilinearity in one fixed row

Fix every row except row $p$. If the new row is $\alpha u+\beta v$, then

$$\det(\text{same rows except }\alpha u+\beta v) =\alpha\det(\text{same rows except }u) +\beta\det(\text{same rows except }v).$$

For $n=1$, the base definition gives

$$\det([\alpha a+\beta b])=\alpha a+\beta b =\alpha\det([a])+\beta\det([b]).$$

For $n\ge2$, fix every row except row $p$. Let matrices $A,B,C$ agree in all those fixed rows, and suppose their $p$th rows satisfy $c_p=\alpha a_p+\beta b_p$. For each column $j$, deleting row $p$ gives the same submatrix:

$$A(p\mid j)=B(p\mid j)=C(p\mid j).$$

Expanding $\det(C)$ along row $p$ and using the entrywise relation $c_{pj}=\alpha a_{pj}+\beta b_{pj}$ gives

$$\begin{aligned} \det(C) &=\sum_{j=1}^{n}(\alpha a_{pj}+\beta b_{pj})(-1)^{p+j}\det(C(p\mid j))\\ &=\alpha\det(A)+\beta\det(B). \end{aligned}$$

The equality works precisely because every other row is held fixed; changing two rows at once is a different statement.

Adjacent swaps and repeated rows

Theorem

Repeated rows force determinant zero

If a square matrix has two identical rows, then its determinant is $0$.

Let $A$ have adjacent rows $r_q,r_{q+1}$, and let $B$ be obtained by swapping those two physical rows. Expand $\det(A)$ along row $q$. Expand $\det(B)$ along row $q+1$, where the row $r_q$ has moved. For each column $j$, the retained submatrix in the two expansions is the same matrix: deleting the position occupied by $r_q$ leaves the other row in the same order. However, the signs differ:

$$(-1)^{q+1+j}=-(-1)^{q+j}.$$

The entries and minors therefore match term by term with the opposite sign, so $\det(B)=-\det(A)$. Swapping rows in positions $p\lt q$ can be realised by $2(q-p)-1$ adjacent swaps, an odd number, and hence also changes the sign.

If rows $p$ and $q$ of $A$ are identical, the matrix obtained by swapping them is still $A$. The swap result then gives $\det(A)=-\det(A)$. Since the entries are real, this implies $2\det(A)=0$ and therefore $\det(A)=0$. This proof does not rely on a later row-replacement rule.

Indexing and strategy

For each term, keep three objects visible: the selected entry, its submatrix after deleting one row and one column, and the minor obtained by taking that submatrix determinant. Write the checkerboard sign from the original row and column positions before evaluating the minor. When a minor is expanded again, its local indices guide the inner sign; they do not replace the outer sign.

The arbitrary-row and arbitrary-column theorem makes the choice of expansion line strategic. Choose a line with many zeros or simple surviving minors, and state that choice before calculating. A zero entry removes a branch immediately, whereas a zero minor must be established by its own calculation. The recursive first-row formula defines the determinant; arbitrary-line expansion is the theorem that permits this computational choice.

Reversible operations and their matrices

Definition

Elementary row operations and elementary matrices

Work over the real numbers. Let $A$ be an $n\times n$ matrix. An elementary row operation is one of the following, with the indicated row indices distinct when two rows occur:

1. $R_p\leftrightarrow R_q$: interchange rows $p$ and $q$;
2. $R_p\leftarrow\beta R_p$, where $\beta\ne0$;
3. $R_q\leftarrow R_q+\alpha R_p$.

The corresponding elementary matrix $E$ is obtained by applying that operation to $I_n$. Left multiplication gives the same operation on every $n\times m$ matrix $X$: the transformed matrix is $EX$. The restriction $\beta\ne0$ is essential for an elementary operation because it makes the operation reversible.

The determinant scaling rule itself still holds for $\beta=0$: a zero row gives determinant zero. However, zero scaling is not reversible and therefore is not an elementary factor in a product that is being undone. Keeping these two facts separate prevents a zero factor from being cancelled later.

Finite elimination and elementary inverses

For a real $m\times n$ matrix, scan columns from left to right in the rows below the last chosen pivot. If an available column has a nonzero entry, move it to the next pivot position by a swap, scale by its nonzero reciprocal, and subtract multiples of this row to clear entries below. If no entry is available in that column, move to the next column. There are at most $\min(m,n)$ pivots and finitely many arithmetic operations, so this constructs REF. Clearing pivot columns above from the last pivot upward constructs RREF and does not disturb earlier pivot columns. In a homogeneous RREF system, any free variable can be assigned, and back substitution uniquely determines pivot variables. Setting one free variable to one and the others to zero therefore gives a nonzero homogeneous solution. With no free variable the only homogeneous solution is zero.

An elementary matrix is the result of applying one legal row operation to $I_m$. Its row-column product with any $m\times n$ matrix performs that same operation. The reverse operation is respectively the same swap, scaling by $1/\beta$ for $\beta\ne0$, or adding $-\alpha$ times the source row. Its elementary matrix $E^{-1}$ satisfies $E^{-1}E=EE^{-1}=I_m$, because the two compositions restore every row of $I_m$. A finite product of elementary matrices is invertible by applying their inverses in reverse order; associativity verifies both inverse identities. These facts supply the elimination and reversible-factor hypotheses in the following square-matrix equivalence proof.

Equivalent formulations

Theorem

Equivalent ways to recognize invertibility

Let $A$ be a real $p\times p$ matrix. The following conditions are equivalent:

1. $A$ is invertible.
2. $A$ is row-equivalent to $I_p$.
3. $A$ is a product of elementary row-operation matrices of order $p$.
4. $A$ has a left inverse.
5. $A$ has a right inverse.
6. $A$ is nonsingular: $Ax=0$ has only the zero solution.
7. For every $b\in\mathbb R^p$, the system $Ax=b$ is consistent.
8. For every $b\in\mathbb R^p$, the system $Ax=b$ has exactly one solution.

Equivalently, the columns of $A$ are linearly independent, or they span $\mathbb R^p$. When these conditions hold, the unique solution is $A^{-1}b$.

Proof

Where the square hypothesis enters the equivalence proof

A left inverse $H$ forces the homogeneous solution to be zero: if $Ax=0$, then $x=HAx=0$. Conversely, suppose the homogeneous system has only the zero solution. In any RREF of $A$, a free variable would produce a nonzero homogeneous solution. Thus every column has a pivot. Because $A$ is square, there are also exactly $p$ pivot rows, and the RREF is $I_p$.

If a row-operation product $E$ satisfies $EA=I_p$, the reverse chain shows that $E$ is invertible and $A=E^{-1}$. Hence $A$ is invertible and is itself a product of elementary matrices. Conversely, any such product is invertible, and an inverse is in particular a left inverse. This connects conditions 1–4 and 6 without assuming uniqueness of RREF.

Now suppose $AG=I_p$. Then $A$ is a left inverse of the square matrix $G$. The already proved left-inverse criterion makes $G$ invertible, and $A=A(GG^{-1})=(AG)G^{-1}=G^{-1}$ is invertible. This proves the right-inverse criterion without silently reversing a product.

If every $Ax=b$ is consistent, choose solutions $u_j$ of $Au_j=e_j$, where $e_j$ is column $j$ of $I_p$. Their matrix $U=[u_1\ \cdots\ u_p]$ satisfies $AU=I_p$, so the right-inverse criterion applies. Finally, when $A$ is invertible, $A(A^{-1}b)=b$ proves existence, and any solution $x$ satisfies $x=A^{-1}Ax=A^{-1}b$, proving uniqueness. Uniqueness for every right-hand side implies consistency for every right-hand side.

The column statements are translations: independence means that $Ax=0$ has only the zero coefficient vector, and spanning means that every $b$ has a representation $Ax=b$. Thus no additional assumption about the columns is being introduced.

The multiplier for each row operation

Theorem

The three row-operation determinant rules

For an $n\times n$ matrix $A$, with $1\le p,q\le n$ and $p\ne q$ whenever two row indices occur:

1. If $B$ results from $A$ by $R_p\leftrightarrow R_q$, then $\det(B)=-\det(A)$.
2. If $B$ results from $A$ by $R_p\leftarrow\beta R_p$, then $\det(B)=\beta\det(A)$, including the identity at $\beta=0$.
3. If $B$ results from $A$ by $R_q\leftarrow R_q+\alpha R_p$ with $p\ne q$, then $\det(B)=\det(A)$.

The first rule is the alternating property of the determinant. For the second, hold every row except row $p$ fixed and use linearity in that row. If $a_p$ is replaced by $\beta a_p$, the determinant is multiplied by $\beta$.

For a replacement, the row indices must be distinct. If $R_p\leftarrow R_p+\alpha R_p$, the new row is $(1+\alpha)a_p$, so the determinant is multiplied by $1+\alpha$.

Proof

Derive the row-replacement rule from multilinearity

Write the rows of $A$ as $a_1,\ldots,a_n$, and let $C$ be obtained by replacing row $q$ by $a_q+\alpha a_p$, where $p\ne q$. Construct $A^\star$ by replacing row $q$ of $A$ by $a_p$. The $q$th row of $C$ is

$$a_q+\alpha a_p=1\cdot a_q+\alpha\cdot a_p.$$

All other rows of $C$, $A$, and $A^\star$ agree. Therefore multilinearity in row $q$ gives

$$\det(C)=\det(A)+\alpha\det(A^\star).$$

Rows $p$ and $q$ of $A^\star$ are identical, so the alternating property gives $\det(A^\star)=0$. Hence $\det(C)=\det(A)$. This proof also shows exactly which distinct-row assumption makes the extra term vanish.

Theorem

The mixed-operation ledger

Suppose a sequence of elementary operations changes $A$ into $U$. If the sequence contains $s$ swaps and scales rows by nonzero factors $\beta_1,\ldots,\beta_q$, then

$$\det(U)=(-1)^s\left(\prod_{j=1}^{q}\beta_j\right)\det(A).$$

Consequently,

$$\det(A)=\frac{\det(U)}{(-1)^s\prod_{j=1}^{q}\beta_j}.$$

Row replacements do not appear in the product because their multiplier is $1$.

If $U$ is a square row-echelon matrix, it is upper triangular and $\det(U)$ is the product of its diagonal entries. A zero row makes this product zero, so the ledger immediately gives $\det(A)=0$ because its denominator contains only nonzero factors. If this row-echelon matrix has no zero row, each of its $n$ diagonal positions is a pivot, so the diagonal product is nonzero. An arbitrary upper triangular matrix need not have this property: for example, $\begin{bmatrix}0&1\\0&1\end{bmatrix}$ is upper triangular but has zero determinant. The row-echelon qualification is therefore essential.

A disciplined row-reduction algorithm

Before starting, write the matrix size and mark the roles of the rows. At each stage, use only a legal elementary operation: the two row indices in a swap or replacement must be distinct, and every scaling factor recorded in the ledger must be nonzero. Then follow this sequence:

1. Reduce the entries below each pivot, using row replacements whenever they suffice. Record a swap immediately when a pivot must be moved.
2. If a pivot row is normalized, record its factor $\beta$ with its sign and position in the sequence. The final diagonal product belongs to the scaled matrix, so this factor will be divided out.
3. Stop at an upper triangular matrix. If a zero row appears, stop there: no later division by a supposed pivot is justified, and the determinant is already certified to be zero.
4. Multiply the diagonal entries of the final triangular matrix. Finally apply $\det(A)=\det(U)/((-1)^s\prod\beta_j)$, rather than trying to remember the corrections mentally.

This algorithm permits different valid elimination choices. Two reduction paths may produce different triangular matrices and different intermediate pivots, but their ledgers must return the same determinant. That agreement is a useful check on arithmetic, while the theorem explains why it is guaranteed. The same discipline also applies to an augmented matrix: when solving $Ax=b$, an elementary operation acts on $[A\mid b]$ as a whole, whereas determinant bookkeeping concerns the square coefficient matrix $A$.

From elementary factors to a product theorem

For one elementary operation, let $E$ be its matrix. When $X$ is also square of the same size, $EX$ is square. Since $E$ is the result of applying the operation to $I_n$, the row rules say $\det(E)$ is respectively $-1$, $\beta$, or $1$. Applying the same rule to $X$ gives

$$\det(EX)=\det(E)\det(X).$$

If $E_s\cdots E_1$ is a sequence, induction on the number of factors gives

$$\det(E_s\cdots E_1X)= \left(\prod_{j=1}^{s}\det(E_j)\right)\det(X).$$

Now suppose $A$ is invertible. The earlier row-reduction theorem supplies a factorization $A=E_s\cdots E_1$. Applying the last formula first to $I_n$ and then to $B$ yields

$$\det(A)=\prod_j\det(E_j)\ne0, \qquad \det(AB)=\left(\prod_j\det(E_j)\right)\det(B).$$

Thus $\det(AB)=\det(A)\det(B)$ in the invertible case.

For the singular case, row-reduce $A$ to an echelon form $R$. The invertibility dictionary from the earlier notes says that a singular square matrix has a zero row in $R$. Let $E_s\cdots E_1A=R$ and set $c=\prod_j\det(E_j)$. Every factor is nonzero because every operation is reversible. The zero row of $R$ remains a zero row in $RB$, so

$$c\det(A)=\det(R)=0, \qquad c\det(AB)=\det(RB)=0.$$

Since $c\ne0$, cancellation gives $\det(A)=0$ and $\det(AB)=0$. The equality again follows, now with both sides zero.

The notation $E_s\cdots E_1A$ also records the order of operations. The rightmost factor $E_1$ acts first, then $E_2$, and so on. No commutativity of matrices is being used in this argument. The factors are all $n\times n$, while $B$ is an $n\times n$ matrix, so each intermediate product is defined. This dimensional condition is part of the theorem, not a cosmetic convention.

Theorem

Determinant of a product

If $A$ and $B$ are square matrices of the same size, then

$$\det(AB)=\det(A)\det(B).$$

This statement was proved by the two cases above. It is stronger than a calculation trick: although $AB$ and $BA$ can be different matrices, scalar multiplication commutes, so

$$\det(AB)=\det(A)\det(B)=\det(B)\det(A)=\det(BA).$$

Determinant and invertibility

Theorem

Determinant criterion for invertibility

For a square matrix $A$,

$$A\text{ is invertible}\quad\Longleftrightarrow\quad\det(A)\ne0.$$

The proof of the product theorem already establishes both directions: an invertible matrix factors into elementary matrices with nonzero determinants, while a singular matrix reduces to an echelon matrix with a zero row. The nonzero reduction multiplier transfers that zero determinant to the original matrix.

The adjugate identity and continuity of inversion

For $n\ge2$, let $C_{ij}=(-1)^{i+j}\det(A(i\mid j))$ and define $\operatorname{adj}(A)_{ji}=C_{ij}$. The $(i,j)$ entry of $A\operatorname{adj}(A)$ is $\sum_k a_{ik}C_{jk}$. If $i=j$, row expansion makes this $\det A$. If $i\ne j$, it is the row-$j$ expansion of the matrix obtained by replacing row $j$ by row $i$: its row-$j$ cofactors are unchanged, and its repeated rows make its determinant zero. Hence $A\operatorname{adj}(A)=(\det A)I$.

The permutation formula also gives $\det(A^T)=\det A$: replace a permutation by its inverse. Their inversion numbers agree, since an inversion $(r,s)$ corresponds to the inversion $(\sigma(s),\sigma(r))$ of the inverse, and their entry products agree after reindexing. This applies to every minor too, so $\operatorname{adj}(A^T)=(\operatorname{adj} A)^T$. Applying the first identity to $A^T$ and transposing yields $\operatorname{adj}(A)A=(\det A)I$. For $n=1$, define $\operatorname{adj}([a])=[1]$ and both identities are immediate.

When $\det A\ne0$, the two identities prove $A^{-1}=\operatorname{adj}(A)/\det A$. Each determinant and cofactor is a finite polynomial in matrix entries; thus this inverse formula is continuous wherever the determinant is nonzero. This supplies the continuity assertion used in the local inverse-function proof.

Proofs are given in triangular determinants and the determinant criterion.

Simultaneous Models: Valuation and Production Balances

Fixed weights give a linear valuation

Assign the fixed weights $d=(0.9,0.8)^T$ to two future payments. For the payment vector $c=(100,50)^T$, the weighted value is

$$d^Tc=0.9(100)+0.8(50)=130.$$

With the weights fixed, combining payment vectors combines their weighted values. If the weights depend on the payments or another changing input, that larger model need not be linear.

Three balances, one simultaneous solution

Suppose three quantities satisfy

$$x+y+z=6,\qquad2x-y+z=3,\qquad x+2y+3z=14.$$

Subtract twice the first equation from the second, and subtract the first from the third. The lower equations become $-3y-z=-9$ and $y+2z=8$. Add the former to three times the latter: $5z=15$. Thus $z=3$, $y=2$, and $x=1$. Substituting gives $6$, $3$, and $14$ in the three original left sides. The nonzero pivots determine every variable, so the solution is unique.

Gross output is not the same as final demand

Let $x$ be gross output, $Ax$ the internal use of those outputs, and $d$ final demand. A fixed-coefficient balance is

$$x=Ax+d,\qquad (I-A)x=d.$$

Take

$$A=\begin{pmatrix}0.2&0.1\\0.1&0.2\end{pmatrix},\qquad d=\begin{pmatrix}70\\70\end{pmatrix}.$$

Then $I-A=\begin{pmatrix}0.8&-0.1\\-0.1&0.8\end{pmatrix}$ has determinant $0.63\ne0$. The vector $x=(100,100)^T$ solves the balance: internal use is $(30,30)^T$, and adding final demand gives $(100,100)^T$. Nonsingularity proves uniqueness, while nonnegativity and the direct balance verify feasibility for this demand.

A positive determinant alone is not a nonnegative-output guarantee. For example, $A=2I_2$ and $d=(1,1)^T$ give $\det(I-A)=1>0$, but the unique algebraic solution is $x=(-1,-1)^T$. That solution is not feasible when outputs must be nonnegative. Solvability and model feasibility are different checks.

Order changes a matrix action

Let $D=\begin{pmatrix}2&0\\0&1\end{pmatrix}$ scale the first coordinate and $S=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ exchange coordinates. Then

$$DS=\begin{pmatrix}0&2\\1&0\end{pmatrix},\qquad SD=\begin{pmatrix}0&1\\2&0\end{pmatrix}.$$

Scaling after the exchange differs from exchanging after the scale. For square matrices, $(A+B)^2=A^2+AB+BA+B^2$; the middle terms combine as $2AB$ only if $AB=BA$.

A parameter can change the number of solutions

For $x+2y=5$, $2x+ay=b$, elimination gives $(a-4)y=b-10$. If $a\ne4$, there is one solution: $y=(b-10)/(a-4)$ and $x=5-2y$. If $a=4,b=10$, every $(5-2t,t)$ solves it. If $a=4,b\ne10$, there is no solution. Dividing by $a-4$ before separating these cases would discard both singular possibilities.

Verify an inverse by substitution

For $A=\begin{pmatrix}3&1\\1&1\end{pmatrix}$, the determinant is $2$, so $A^{-1}=\frac12\begin{pmatrix}1&-1\\-1&3\end{pmatrix}$. Applied to $(10,6)^T$, this gives $(2,4)^T$. The original equations check as $3(2)+4=10$ and $2+4=6$.

Practice with full solutions

P01. Compute $Aq$ for $A=\begin{pmatrix}1&3\\2&0\end{pmatrix}$ and $q=(2,4)^T$.

Solution. $Aq=(2+12,4+0)^T=(14,4)^T$.

P02. Compute $AB$ and $BA$ for $A=\begin{pmatrix}1&1\\0&1\end{pmatrix}$ and $B=\begin{pmatrix}2&0\\0&3\end{pmatrix}$.

Solution. $AB=\begin{pmatrix}2&3\\0&3\end{pmatrix}$ and $BA=\begin{pmatrix}2&2\\0&3\end{pmatrix}$. Their off-diagonal entries differ, so the order matters.

P03. Is $L(x)=2x+(1,0)^T$ linear on $\mathbb R^2$? Give a decisive test.

Solution. $L(0)=(1,0)^T\ne0$. Every linear map sends zero to zero, so this map is not linear.

P04. Solve $x+y+z=4$, $x-y+z=2$, and $2x+y-z=3$ by elimination.

Solution. Subtract the second equation from the first: $2y=2$, so $y=1$. The remaining equations give $x+z=3$ and $2x-z=2$. Adding gives $3x=5$, hence $x=5/3$ and $z=4/3$. Substitution into the original equations verifies all three right sides.

P05. Find all solutions of $x+2y-z=3$ and $2x+4y-2z=6$.

Solution. The second equation is twice the first. Set $y=s,z=t$; then $x=3-2s+t$. Thus every solution is $(3-2s+t,s,t)^T$, where $s,t\in\mathbb R$. Substituting this expression verifies both equations for every parameter pair.

P06. Classify $x-y=2$, $2x+ay=b$ for all real $a,b$.

Solution. Subtract twice the first equation from the second: $(a+2)y=b-4$. If $a\ne-2$, then $y=(b-4)/(a+2)$ and $x=2+y$, the unique solution. If $a=-2,b=4$, all $(2+t,t)$ solve it. If $a=-2,b\ne4$, the reduced equation is contradictory and there is no solution.

P07. Find the inverse of $A=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ and use it to solve $Ax=(5,4)^T$.

Solution. The determinant is $3$, so $A^{-1}=\frac13\begin{pmatrix}2&-1\\-1&2\end{pmatrix}$. Multiplication gives $x=(2,1)^T$. The check is $(4+1,2+2)^T=(5,4)^T$.

P08. Find the determinant of $\begin{pmatrix}1&2&0\\0&2&3\\0&0&4\end{pmatrix}$ and decide invertibility.

Solution. The matrix is triangular, so its determinant is $1\cdot2\cdot4=8\ne0$. Therefore it is invertible.

P09. In $x=Ax+d$, let $A=\operatorname{diag}(1/4,1/2)$ and $d=(30,20)^T$. Find gross output and verify internal use plus final demand.

Full solution. The equations are $(3/4)x_1=30$ and $(1/2)x_2=20$, so $x=(40,40)^T$. Internal use is $(10,20)^T$; adding demand gives $(40,40)^T$. Every quantity is nonnegative, so the algebraic solution also satisfies the stated output constraint.

P10. Prove the particular-plus-null description of a consistent real linear system in both directions. Explain why its entire solution set cannot contain exactly two distinct vectors.

Solution. If $Ax_p=b$ and $Az=0$, then $A(x_p+z)=b$. Conversely, $Ax=b$ implies $A(x-x_p)=0$, so $x=x_p+z$ for a null vector. If two distinct solutions exist, their difference $z\ne0$ is null. Then $x_p+tz$ solves the system for every real $t$. These vectors are distinct for distinct $t$, giving infinitely many solutions rather than exactly two.