Linear systems and accounting models

An accounting identity constrains quantities; it does not determine them automatically. If a company reports total sales and total variable cost for two products, can we recover the quantities sold? Linear algebra tells us whether the evidence gives a unique answer, leaves choices, or contradicts itself. In this chapter we build a model, solve it without losing information, and interpret the result in its original units. All business data below are invented teaching examples.

1 From statements to a matrix equation

Let $x_1,x_2$ denote quantities of two products. Suppose their prices are 30 and 50 currency units, and their unit variable costs are 12 and 20. Sales of 1,600 and variable cost of 640 give

$$30x_1+50x_2=1600,\qquad12x_1+20x_2=640.$$

The second equation is 0.4 times the first. Two reported numbers have supplied only one independent restriction. A solver that returns one pair without explaining the free choice has hidden a feature of the evidence.

A linear system in $n$ unknowns is a list of equations $\sum_{j=1}^n a_{ij}x_j=b_i$, for $1\le i\le m$. Its coefficient matrix $A=(a_{ij})$ is $m\times n$, its unknown vector $x$ is $n\times1$, and its right-hand side $b$ is $m\times1$. The system is $Ax=b$, where

$$(Ax)_i=\sum_{j=1}^n a_{ij}x_j.$$

The columns of $A$ record each unknown's contribution to every measurement. Entries within a row must have compatible units after multiplication by their unknowns. One must not add a currency quantity to a physical quantity just because both are numbers.

The augmented matrix $[A\mid b]$ keeps the system and the observations together. The allowable elementary row operations are exchanging two equations, multiplying an equation by a nonzero scalar, and adding a multiple of one equation to another.

Why these operations preserve the solution set

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.

Reversibility is worth remembering because it separates genuine equivalence moves from destructive shortcuts.

Never apply a row operation to $A$ alone while leaving $b$ fixed: that changes the question.

Finite elimination terminates and preserves the solution set

Let $A\in\mathbb R^{m\times n}$, $b\in\mathbb R^m$, with positive finite integers $m,n$. The permitted row operations are an exchange of two distinct rows, multiplication of a row by a nonzero scalar, and addition of a scalar multiple of one row to a different row. Their inverses are respectively the same exchange, multiplication by the reciprocal, and subtraction of that multiple. Applying an operation to the entire augmented array therefore preserves exactly the solutions of $Ax=b$: the new equations are consequences of the old, and its inverse gives the reverse implication. Each operation is also multiplication on the left by the result of applying it to the identity matrix, an invertible elementary matrix.

Scan the coefficient columns from left to right, maintaining the next unused row. If the current column has a nonzero entry in an unused row, exchange that row into the next position, divide by its nonzero pivot, and subtract multiples of it from every other row to clear that column. Advance the unused-row index. If every unused entry in the column is zero, skip the column. Previously chosen pivot columns remain unit columns: the current unused rows have zeros in them, so the new pivot row and every subsequent subtraction preserve those zeros and earlier pivots. There are only $n$ column scans and at most $\min(m,n)$ pivots, each with finitely many row operations. Thus the algorithm terminates. At its end, the nonzero coefficient rows have increasing pivot columns and zeros below and above each pivot; any remaining coefficient row is zero. This proves the reduced echelon form used below, without assuming it will eventually appear.

Classification and the homogeneous freedom

Write $r$ for the number of pivots in the coefficient part. A zero coefficient row with a nonzero transformed right side is the impossible equation $0=c$, so the system has no solution. Otherwise assign arbitrary real values to all $n-r$ nonpivot variables. In each pivot row, its pivot variable equals the transformed right side minus the displayed linear combination of these free variables; no other pivot variable occurs. These formulas both construct a solution and recover every solution. If $r=n$ the solution is unique. If $r<n$, changing a free variable changes the vector, giving infinitely many solutions.

For $Az=0$ the free variables can all be zero, giving the zero solution. If $r<n$, set one free variable to one and the others to zero, and use the pivot formulas. This constructs a nonzero homogeneous solution. If $r=n$, the formulas force every homogeneous variable to zero. For a consistent system, fixing one solution $x_p$, subtraction proves that every solution has the form $x_p+z$ with $Az=0$, and substitution proves the converse.

For square $A$, if every column has a pivot, the coefficient form is $I$. The product $E$ of the finitely many elementary matrices satisfies $EA=I$. Since $E$ is invertible, $A=E^{-1}$ and therefore also $AE=I$: $E$ is a two-sided inverse. If a pivot is missing, the nonzero homogeneous solution constructed above rules out any inverse. This also justifies applying the same row operations to $[A\mid I]$ to obtain $[I\mid A^{-1}]$ in the invertible case.

2 Elimination and the three possible outcomes

A pivot is a leading nonzero entry in an echelon row. A variable in a pivot column is a pivot variable; other variables are free. Back substitution expresses pivot variables in terms of free variables. A row $[0\;\cdots\;0\mid c]$ with $c\ne0$ is the impossible equation $0=c$.

For the opening example, division and elimination give $3x_1+5x_2=160$ and $0=0$. Thus

$$x_2=t,\qquad x_1=\frac{160-5t}{3}.$$

The algebra permits every real $t$. If quantities must be nonnegative, then $0\le t\le32$. If they must also be integers, $t$ must make $160-5t$ divisible by 3. These are extra modelling conditions, not consequences of row reduction.

Now change product 2's unit cost to 25, and suppose total variable cost is 740. The model becomes

$$30x_1+50x_2=1600,\qquad12x_1+25x_2=740.$$

Subtracting 0.4 times the first equation from the second gives $5x_2=100$. Hence $x_2=20$ and $x_1=20$. Substitution verifies both original observations. A third report that these same sales contain 50 units would contradict this model, since $20+20=40$.

Solution classification. An echelon system is inconsistent exactly when it contains a contradictory row. Otherwise it has one solution if every unknown is a pivot variable, and infinitely many real solutions if a free variable remains.

Justification. With no contradictory row, assign the free variables arbitrarily and determine all pivot variables by back substitution. There is exactly one assignment when there are no free variables. If there is a free variable, distinct choices give distinct vectors. This classification is over $\mathbb R$; a finite field has a different count. $\square$

3 Why a particular solution is not the whole story

The null space is $\ker A=\{z:Az=0\}$. It describes changes invisible to the observations.

Theorem 2 Affine form of all solutions. If $x_p$ solves $Ax=b$, then every solution is uniquely of the form $x_p+z$ with $z\in\ker A$.

Proof. If $Az=0$, then $A(x_p+z)=b$. Conversely, if $Ax=b$, then $A(x-x_p)=b-b=0$. Uniqueness follows from $z=x-x_p$. $\square$

For $3x_1+5x_2=160$, one solution is $(20,20)$ and the null space is the line spanned by $(-5,3)$. All solutions are $(20,20)+s(-5,3)$. Increasing $s$ changes the product mix while preserving the reported totals.

4 A reciprocal cost allocation model

Two service departments have direct costs 80 and 90. Department A receives services worth 20% of B's total cost; B receives services worth 10% of A's total cost. In the stated simplified model,

$$a=80+0.2b,\qquad b=90+0.1a.$$

Substitution gives $0.98a=98$, so $a=100$ and $b=100$. These are gross reciprocal totals, not newly created external expenditure. Adding $a+b$ and calling it the original direct expenditure would count internal services twice. The matrix equation is

$$\begin{pmatrix}1&-0.2\\-0.1&1\end{pmatrix}\binom ab=\binom{80}{90}.$$

Checking units, signs and what is being counted is as important as elimination. If the cross-service coefficients change, the equations change; the result is conditional on that model.

5 Graded practice

E1 Foundation. Solve $x+2y=11$, $3x+4y=25$ and verify your answer.

E2 Interpretation. Solve $2x+3y=12$, $4x+6y=24$. Describe the nonnegative solutions. What changes if the second right-hand side is 25?

E3 Modelling. Two products sell for 20 and 35 per unit. Revenue is 900 and total units sold are 30. Find the quantities and state one assumption needed for this model.

E4 Structural proof. Let $x_p$ solve $Ax=b$. Prove that the system has a unique solution if and only if $\ker A=\{0\}$.

E5 Extension. For $a=d_A+\alpha b$, $b=d_B+\beta a$, derive the unique solution when $1-\alpha\beta\ne0$. Give compatible and incompatible examples when $\alpha\beta=1$.

6 Full solutions

S1. Subtract three times the first equation from the second: $-2y=-8$, so $y=4$ and $x=3$. Checks: $3+8=11$ and $9+16=25$.

S2. The second equation is twice the first. Put $y=t$ and $x=6-3t/2$. Nonnegativity requires $0\le t\le4$. With right-hand side 25, subtraction gives $0=1$, so there is no solution, including no nonnegative solution.

S3. Write $x+y=30$ and $20x+35y=900$. Subtract $20(x+y)=600$ to obtain $15y=300$. Thus $y=20$, $x=10$. This assumes all units use the stated fixed prices and that revenue contains no additional fees or discounts.

S4. By Theorem 2 every solution is $x_p+z$ for $z\in\ker A$. If the null space is zero there is only $x_p$. If it contains nonzero $z$, then $x_p+z\ne x_p$ is a second solution. The assumption that one solution exists is essential.

S5. Substituting gives $(1-\alpha\beta)a=d_A+\alpha d_B$. Hence $a=(d_A+\alpha d_B)/(1-\alpha\beta)$ and $b=(d_B+\beta d_A)/(1-\alpha\beta)$. If $\alpha=\beta=1$ and $d_A=d_B=0$, every $a=b$ solves the equations. If $\alpha=\beta=1$ and $d_A=d_B=1$, adding the equations gives $0=2$, so none do. Positive direct costs with 100% mutual recycling do not define finite totals in this model.

Summary

A linear model connects unknown quantities to observations through $Ax=b$. Reversible row operations expose consistency and free choices. Null vectors identify changes the observations cannot detect. A computed answer becomes an interpretable answer only after checking the original equations, units and application constraints.