The Matrix Form of a Linear Program

A program with forty constraints and sixty variables fills a page in scalars and one line in matrix notation. The compression is useful on its own, and it is not the reason the notation is used.

The reason is that $Ax$ can be read two ways, and the later methods are stated in one or the other. Read by rows, the product recovers each constraint and answers whether a point is allowed. Read by columns, it exhibits the left-hand side as a combination of the columns of $A$, weighted by the variables, which is the reading a basis, a pivot and a reduced cost are all defined in.

A solver's interface asks for the same three objects: a coefficient array, a right-hand-side vector, a cost vector. Assembling them by hand once is what makes that interface legible.

Rows answer whether a point is allowed. Row $i$ holds the coefficients of constraint $i$, so the $i$th entry of $Ax$ is $a_i^{\mathsf{T}}x$: the amount of resource $i$ that the plan $x$ consumes. Comparing it with $b_i$ decides that constraint. Checking feasibility is running down the rows.

Columns answer what a plan is made of. Column $j$ holds everything variable $j$ contributes, one entry per constraint. Running activity $j$ at level $x_j$ consumes $x_j{A}_j$, and the total consumption is the sum:

So $Ax$ is a combination of the columns, with the decision variables as the weights.

The readings describe the same numbers and suit different questions. "The feasible region is an intersection of half-spaces" is a row statement. "A basis is a set of $m$ independent columns" is a column statement. Chapters that seem to describe unrelated objects are often the two readings of one product, which is why moving between them is the competence rather than either one alone.

The shapes are not a convention to memorise; they are forced. $A$ must have one column per variable for $Ax$ to be defined, and one row per constraint for the result to be comparable with $b$. A transposed $A$ usually produces a product that is undefined, and when the dimensions happen to agree it computes something that answers no question in the problem.

Beyond the statement itself, three details decide whether an assembled $A$, $b$ and $c$ are right.

Where each number goes. The coefficient of variable $j$ in constraint $i$ is $a_{ij}$: the row index is the constraint, the column index is the variable. A variable absent from a constraint contributes $0$, and that zero must be written. A shorter row is a different program.

Mixed directions. $Ax\le b$ requires every row to be a $\le$ relation. A constraint written $a^{\mathsf{T}}x\ge \beta$ becomes $-a^{\mathsf{T}}x\le -\beta$, negating both the row and its right-hand side. An equality needs two rows, $a^{\mathsf{T}}x\le \beta$ and $-a^{\mathsf{T}}x\le -\beta$, or a separate equality block $A_{\text{eq}}x=b_{\text{eq}}$. Dropping the direction rather than converting it is the error this produces.

Maximisation. $max{c}^{\mathsf{T}}x$ and $min(-c{)}^{\mathsf{T}}x$ have the same optimal $x$ and objective values differing by sign. The matrix form as written above is a minimisation, so a maximisation is negated on the way in and the reported value negated on the way out.

What the form does not do. It records the program, unchanged. No constraint is removed, no feasible point is added, and the optimum is the same point it was in scalars.

The two readings of $Ax$ are not competing accounts. Each later result is stated in one of them, and knowing which removes most of the difficulty in following it.

A pattern is visible in the table. Questions about a point are row questions: they take an $x$ and test it. Questions about which plans are available are column questions: they select columns and solve for the weights.

The simplex method is a column method throughout, which is why it is stated for programs in the equality form $Ax=b$ rather than for $Ax\le b$. Converting to that form is what makes the columns the objects being selected.

The program. A workshop makes three products. Each unit of product 1 uses 2 machine hours, 1 labour hour and 4 kg of material; product 2 uses 1, 2 and 3; product 3 uses 3, 2 and 5. Available: 120 machine hours, 90 labour hours, 250 kg. Unit profits are 30, 20 and 45. Maximise profit.

Step 1: fix the index order. Variables $x_1,x_2,x_3$ are units of each product. Constraints are ordered machine, labour, material. Both orders are arbitrary and both must then be used consistently.

Step 2: assemble. One row per constraint, one column per variable:

$A$ is $3\times 3$ here because the counts coincide; that is not general.

Step 3: write the program.

As a minimisation, $min(-c{)}^{\mathsf{T}}x$ over the same set, with the reported value negated.

---

Step 4: read a row back. Row 2 is $(1,2,2)$ with $b_2=90$, so constraint 2 is

the labour hours. This is the check that the assembly is right: every row must translate back to a constraint of the original description.

Step 5: read a column back. Column 3 is $(3,2,5{)}^{\mathsf{T}}$: one unit of product 3 uses 3 machine hours, 2 labour hours and 5 kg. A column is an activity's resource profile, not a constraint.

Step 6: evaluate a plan both ways. Take $x=(10,15,20{)}^{\mathsf{T}}$.

By rows:

Every entry is at most the corresponding entry of $b=(120,90,250{)}^{\mathsf{T}}$, so the plan is feasible. Profit is $c^{\mathsf{T}}x=30(10)+20(15)+45(20)=1500$.

By columns:

The same vector. The readings are two groupings of one calculation, and agreeing on every entry is what makes them readings of one object rather than two procedures.

Step 7: a constraint in the wrong direction. Suppose the description also required total output of at least 12 units: $x_1+x_2+x_3\ge 12$. To join $Ax\le b$ it is negated on both sides,

adding the row $(-1,-1,-1)$ with right-hand side $-12$, and making $A$ a $4\times 3$ matrix. At $x=(10,15,20{)}^{\mathsf{T}}$ the new row gives $-45\le -12$, which holds. Dropping the direction instead of negating it is the error this step exists to prevent.

Comparing the vectors as wholes. A reader takes $Ax\le b$ to mean that $Ax$ is shorter than $b$, or that its entries sum to less. With $Ax=(95,80,185{)}^{\mathsf{T}}$ and $b=(120,90,250{)}^{\mathsf{T}}$ both readings happen to agree with the entrywise one, which is why the mistake survives. Take $Ax=(135,90,225{)}^{\mathsf{T}}$ instead: the total is smaller than the total of $b$, and the plan is infeasible, because row 1 gives . The inequality is $m$ separate statements and one failure is enough.

A transposed coefficient matrix. Writing $A$ with one row per variable and one column per constraint makes $Ax$ undefined unless the counts coincide. When they do coincide, a square $A$, as in the worked example, the product is defined and computes nothing the problem asked about: entry $i$ becomes a sum over constraints of the coefficients of variable $i$, which is not a resource total. This is the failure that a units check catches and a shape check does not.

A dropped direction. A constraint $x_1+x_2\ge 12$ entered as the row $(1,1,0)$ with right-hand side $12$ asserts $x_1+x_2\le 12$: the feasible set is now bounded where the description bounded it below. The row is correct and the program is a different one.

Omitted zeros. Variable 3 absent from constraint 1 is recorded as $a_{13}=0$. A row written with two entries because "the third does not appear" either fails to parse or silently shifts every later coefficient one place left, which renames the variables.

What unites the four is that each produces a well-formed object. Nothing about $A$, $b$ or the arithmetic reports the fault; only translating a row back into the sentence it came from does.

Take

for three products and three resources.

Both descriptions are of the same nine numbers. Row 2 and column 2 share only the entry $a_{22}=2$, and they mean different things by it: in the row it is the labour used per unit of product 2, in the column it is the same quantity seen as part of product 2's resource profile. That the two readings agree on every entry is what makes the matrix one object rather than two tables.

The practical use of the distinction is diagnostic. A reader stuck on "what is $A_B^{-1}{A}_j$" is usually reading rows in a column statement. Naming the reading in force is often the whole of the difficulty.