3. Vectors, Matrices, Determinants, and Feasibility

Learning goals and preparation

We assume Chapter 1's equations and Chapter 2's coordinate geometry. This chapter organizes several quantities at once. You will calculate vector totals and weighted values, multiply and transpose matrices, solve simultaneous equations by reversible operations, and use determinants without confusing algebraic uniqueness with model feasibility.

3.1 Vectors record several quantities

A vector is an ordered list, usually written as a column. If $q=(q_1,q_2)^T$ records quantities of two goods and $p=(p_1,p_2)^T$ their prices per unit, total value is the dot product $p^Tq=p_1q_1+p_2q_2$. Components have meanings; exchanging them changes the recorded object unless the interpretation is exchanged too.

Worked example 1: aggregate baskets. Let baskets be $q=(3,2)^T$, $r=(1,5)^T$, and prices $p=(4,6)^T$. Two copies of the first and one of the second give $2q+r=(7,9)^T$, with value $p^T(2q+r)=82$. Linearity also gives $2p^Tq+p^Tr=2(24)+34=82$. Prices are fixed in this calculation; if they changed with quantity, valuation would not generally remain linear.

For compatible coordinate units, $\|v\|=\sqrt{v^Tv}$ is Euclidean length and $u\perp v$ means $u^Tv=0$. Different economic units should not be silently treated as interchangeable geometric lengths. Rescaling one variable changes distances even when the underlying recorded situation is the same.

A vector $v$ is a linear combination of $u_1,\ldots,u_k$ if $v=c_1u_1+\cdots+c_ku_k$ for some real coefficients. A list is independent if its only zero combination has every coefficient zero. Two nonzero plane vectors are dependent exactly when one is a scalar multiple of the other.

3.2 Matrix arithmetic encodes table operations

An $m\times n$ matrix has $m$ rows and $n$ columns. Add equal-size matrices and multiply by scalars entrywise. For $A$ of size $m\times n$ and $B$ of size $n\times p$,

$$(AB)_{ij}=\sum_{k=1}^n a_{ik}b_{kj}.$$

The product has size $m\times p$. The inner dimensions must agree. Column $j$ of $AB$ is $A$ times column $j$ of $B$, which explains multiplication as applying one table's linear rule to several inputs at once.

Worked example 2: resources for several plans. Suppose

$$A=\begin{pmatrix}2&1\\1&4\end{pmatrix},\qquad Q=\begin{pmatrix}3&5\\2&1\end{pmatrix}.$$

Each column of $Q$ is a production plan, and each column of $A$ is the resource use per unit of one product. Then $AQ=\begin{pmatrix}8&11\\11&9\end{pmatrix}$ records resource totals for the two plans. The first row and second row may use different resource units; additions occur only within a compatible row.

Matrix multiplication is associative and distributive but not generally commutative. For $A=\begin{pmatrix}1&1\\0&1\end{pmatrix}$, $B=\begin{pmatrix}1&0\\1&1\end{pmatrix}$, $AB=\begin{pmatrix}2&1\\1&1\end{pmatrix}$ whereas $BA=\begin{pmatrix}1&1\\1&2\end{pmatrix}$. The transpose satisfies $(A^T)_{ij}=a_{ji}$ and $(AB)^T=B^TA^T$. An identity matrix has ones on the diagonal and zeros elsewhere, acting like multiplication by one at the correct size.

3.3 Simultaneous equations and reversible elimination

A linear system $Ax=b$ imposes all its equations at once. Store it as $[A\mid b]$. Swapping equations, multiplying one by a nonzero constant, or adding a multiple of one to another preserves exactly the solution set: each step can be undone. Multiplying an equation by zero is not allowed because it destroys a constraint.

Worked example 3: recover two prices. Suppose baskets give $2p+q=11$ and $p+3q=13$. Subtract twice the second equation from the first to get $-5q=-15$, so $q=3$ and $p=4$. Both original values check. It is not enough to solve one equation: infinitely many pairs satisfy it alone.

A row of zeros with nonzero right side means inconsistency. A completely zero row is redundant. If an unknown is not forced by a pivot, describe it using a free parameter.

Worked example 4: dependence versus inconsistency. If $x+2y=6$ and $2x+4y=12$, the second repeats the first, and all $(6-2t,t)$ are solutions. If the second right side is instead $13$, subtracting twice the first gives $0=1$, so there are no solutions. Similar-looking coefficient tables can therefore behave differently depending on their right sides.

For real systems there cannot be exactly two solutions and no others. If $x_1,x_2$ are distinct solutions, then $x_1+t(x_2-x_1)$ solves the same system for every real $t$, by distributivity. This proves infinitely many rather than merely suggesting it from a diagram.

3.4 Determinants and inverse matrices

For a $2\times2$ matrix, $\det\begin{pmatrix}a&b\\c&d\end{pmatrix}=ad-bc$. A nonzero determinant means the two coefficient columns are independent and the square system has a unique solution for every right side. The inverse is

$$A^{-1}=\frac1{ad-bc}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}.$$

Multiplying this by $A$ in both orders gives $I$, proving the formula. The unique solution is $x=A^{-1}b$. If $ad-bc=0$, this formula cannot be used; classify the right side by elimination instead.

For an $n\times n$ matrix $A=(a_{ij})$ with $n\ge2$, let $M_{ij}$ be the matrix obtained by deleting row $i$ and column $j$. Its cofactor is $C_{ij}=(-1)^{i+j}\det M_{ij}$. Expansion along any fixed row $i$ gives

$$\det A=\sum_{j=1}^n a_{ij}C_{ij}.$$

The base case is $\det(a_{11})=a_{11}$ for a $1\times1$ matrix. For example,

$$\det\begin{pmatrix}2&1&0\\1&2&1\\0&1&2\end{pmatrix}=2(4-1)-1(2-0)=4.$$

Elimination gives another calculation route: swapping rows reverses determinant sign, scaling one row scales the determinant by that factor, and adding a row multiple leaves it unchanged. A triangular determinant is the product of diagonal entries. These rules connect determinant zero with a missing pivot and singularity.

Worked example 5: no inverse by division at a singular parameter. For $A(a)=\begin{pmatrix}1&2\\2&a\end{pmatrix}$, determinant is $a-4$. It is invertible only when $a\ne4$. At $a=4$, the second coefficient row is twice the first; the right side must have the same relationship for consistency. An expression containing $1/(a-4)$ is not a solution formula for the excluded case.

3.5 Feasibility and linear inequality models

Solving equalities does not automatically satisfy nonnegativity or capacity constraints. A feasible set collects every point satisfying all conditions. In the plane, a non-strict linear inequality $ax+by\le c$ with $(a,b)\ne(0,0)$ describes a closed half-plane. A finite intersection of such closed half-planes that is nonempty, bounded, and has nonempty two-dimensional interior is a convex polygon. An intersection may instead be empty, a line segment, a point, or unbounded; such cases need separate treatment.

Worked example 6: a small resource model. Suppose $x,y\ge0$ and resource limits are $x+y\le4$, $2x+y\le6$. A hypothetical objective is $P=3x+2y$. The feasible vertices are $(0,0)$, $(3,0)$, $(2,2)$, and $(0,4)$. The intersection $(2,2)$ comes from solving the two active resource equalities. Objective values at the vertices are $0,9,10,8$, so the maximum is $10$ at $(2,2)$.

Why is checking vertices enough here? A nonconstant affine objective cannot have a strict maximum in the interior, because a small move in its increasing direction raises it. On each edge the objective is affine in one parameter, so its maximum occurs at an endpoint unless it is constant along the edge, in which case the endpoints attain the same maximum too. Compactness ensures attainment. This is an elementary geometric argument for a bounded polygon, not a claim that every nonlinear constrained problem is solved at a vertex.

If quantities must be whole numbers, integer feasibility is an additional condition. This example's maximizing vertex is integral, but a general continuous optimum need not be. Rounding independently can violate a resource inequality.

3.6 Graded exercises

Foundation

1. With $p=(2,5)^T$ and $q=(4,3)^T$, calculate $p^Tq$. Interpret it when components are prices and quantities.
2. Calculate $Aq$ for $A=\begin{pmatrix}3&1\\0&2\end{pmatrix}$ and $q=(2,5)^T$.
3. State the sizes of $AB$ and $BA$ if $A$ is $2\times3$ and $B$ is $3\times2$.

Core

4. Solve $3x+y=14$, $x+2y=8$ and verify both equations.
5. Find every solution of $x-y=3$, $2x-2y=6$.
6. Decide whether $x+2y=1$, $3x+6y=4$ is consistent.
7. Find the inverse of $A=\begin{pmatrix}2&1\\1&1\end{pmatrix}$ and use it to solve $Ax=(7,4)^T$.
8. Compute the determinant of $\begin{pmatrix}1&0&2\\0&2&0\\3&0&1\end{pmatrix}$ by expanding along a sparse row or column.

Synthesis

9. Maximize $2x+y$ over $x,y\ge0$, $x+y\le3$. Explain whether the maximizing point is unique.
10. Prove that if $Au=Av$, then $A(u-v)=0$. Explain why an invertible $A$ forces $u=v$, and give a singular example where distinct inputs have the same output.

3.7 Full solutions

1. $p^Tq=2(4)+5(3)=23$. With compatible price/quantity units it is total value, not the vector of quantities or average price.
2. The result is $(3(2)+5,0+2(5))^T=(11,10)^T$.
3. $AB$ is $2\times2$, and $BA$ is $3\times3$. Both exist but cannot be equal because they have different sizes.
4. Subtracting three times the second equation from the first gives $-5y=-10$, so $y=2$ and $x=4$. Checks: $12+2=14$ and $4+4=8$.
5. The second equation is redundant. Let $y=t$, giving every solution $(3+t,t)$.
6. Subtract three times the first equation from the second: $0=1$. The system is inconsistent.
7. The determinant is $1$, so $A^{-1}=\begin{pmatrix}1&-1\\-1&2\end{pmatrix}$. Multiplying by $(7,4)^T$ gives $(3,1)^T$. Check: $(6+1,3+1)^T=(7,4)^T$.
8. Expand along row two: $2\det\begin{pmatrix}1&2\\3&1\end{pmatrix}=2(1-6)=-10$.
9. Vertices are $(0,0),(3,0),(0,3)$ with objective values $0,6,3$. The unique maximum is $6$ at $(3,0)$. Directly, $2x+y=(x+y)+x\le3+3=6$, and equality forces $x=3,y=0$.
10. Distributivity gives $A(u-v)=Au-Av=0$. If $A$ is invertible, multiply by $A^{-1}$ to get $u-v=0$. For $A=\begin{pmatrix}1&0\\0&0\end{pmatrix}$, the distinct vectors $(1,0)^T$ and $(1,2)^T$ both map to $(1,0)^T$.

Summary and onward map

Vectors retain the order and meaning of quantities. Matrix multiplication combines compatible linear rules and depends on order. Reversible elimination classifies systems, while determinants and inverses handle nonsingular square cases. Feasibility adds model constraints to algebraic solutions. Linear inequality geometry provides a first application of simultaneous constraints without assuming calculus.

Proofs supporting the methods used in this note

Proof of the finite real matrix product laws

Let $m,n,p,q$ be positive integers, let $A\in\mathbb R^{m\times n}$, $B\in\mathbb R^{n\times p}$, and $C\in\mathbb R^{p\times q}$. All the following arguments use the row-by-column definition and finite real sums. For any output position $(i,\ell)$,

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

The middle equality only reorders two finite sums and uses real distributivity. Both products are $m\times q$, so equality at every position proves associativity. No factor has changed its order.

For $D\in\mathbb R^{n\times p}$, the same definition gives

$$[A(B+D)]_{ik}=\sum_{j=1}^{n}a_{ij}(b_{jk}+d_{jk}) =(AB)_{ik}+(AD)_{ik}.$$

For $E\in\mathbb R^{m\times n}$, it gives

$$[(A+E)B]_{ik}=\sum_{j=1}^{n}(a_{ij}+e_{ij})b_{jk} =(AB)_{ik}+(EB)_{ik}.$$

Thus both distributive laws hold with the displayed matching sizes. For every real scalar $c$,

$$[(cA)B]_{ik}=\sum_j(ca_{ij})b_{jk} =c\sum_j a_{ij}b_{jk} =\sum_j a_{ij}(cb_{jk})=[A(cB)]_{ik},$$

proving $(cA)B=c(AB)=A(cB)$ by entrywise equality. In particular, for $x,y\in\mathbb R^n$ and real $s,t$,

$$[A(sx+ty)]_i=\sum_j a_{ij}(sx_j+ty_j) =s(Ax)_i+t(Ay)_i.$$

This proves the matrix-vector linearity used when comparing solutions of the same linear system. All identities concern compatible finite real matrices; they do not assert commutativity or cancellation of arbitrary matrix factors.

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.