The Matrix Form of a Linear Program

Collecting the coefficients of a linear program into a matrix and its data into vectors replaces $m$ written constraints with one statement, $A x \leq b$ . The compression is not cosmetic: the row reading recovers the individual constraints, the column reading exhibits $A x$ as a combination of the columns of $A$ , and every later method is stated in terms of one reading or the other.

Definition

A linear program written out in scalars,

\begin{aligned} min & c_{1} x_{1} + \dots + c_{n} x_{n} \\ subject to & a_{11} x_{1} + \dots + a_{1 n} x_{n} \leq b_{1}, \\ ⋮ \\ a_{m 1} x_{1} + \dots + a_{m n} x_{n} \leq b_{m}, \\ x_{1}, \dots, x_{n} \geq 0, \end{aligned}

is written in matrix form as

min c^{T} x subject to A x \leq b, x \geq 0,

where $A \in R^{m \times n}$ holds the constraint coefficients, $b \in R^{m}$ the right-hand sides, $c \in R^{n}$ the objective coefficients, and $x \in R^{n}$ the variables.

The shapes are forced by the arithmetic. $A$ has one row per constraint and one column per variable, so $A x$ is an $m$ -vector comparable with $b$ . The objective $c^{T} x$ is a $1 \times n$ row times an $n$ -vector, giving a scalar.

The inequality is entrywise. $A x \leq b$ abbreviates $m$ separate scalar inequalities, one per row. It is not a statement about vector magnitude or ordering in any other sense.

Row reading. Row $i$ of $A$ is the coefficient vector $a_{i}^{T}$ of constraint $i$ , and the $i$ th entry of $A x$ is the dot product $a_{i}^{T} x$ . Reading by rows recovers the original constraints one at a time.

Column reading. Column $j$ of $A$ is the vector $A_{j}$ of coefficients that variable $j$ contributes, one entry per constraint, and

A x = x_{1} A_{1} + x_{2} A_{2} + \dots + x_{n} A_{n} .

Reading by columns exhibits the left-hand side as a combination of the columns, with the variables as weights.

Formal statement

$A \in R^{m \times n}$ , $b \in R^{m}$ , $c \in R^{n}$ . The feasible set is ${x \in R^{n} : A x \leq b, x \geq 0}$ , and the program seeks $x$ in that set minimising $c^{T} x$ . The $i$ th row of $A x \leq b$ is $a_{i}^{T} x \leq b_{i}$ ; the column expansion is $A x = \sum_{j = 1}^{n} x_{j} A_{j}$ .

Assumptions and scope

The relation $A x \leq b$ holds entrywise: it abbreviates $m$ scalar inequalities and asserts nothing about norms or about any other ordering of vectors.
The shapes must agree. $A$ is $m \times n$ with one row per constraint and one column per variable, so $A x$ is an $m$ -vector; a transposed $A$ produces a product that is defined only by accident and means something else.
Sign restrictions are stated separately from $A x \leq b$ . Writing $x \geq 0$ as extra rows of $A$ is possible but changes which rows the later theory counts as constraints.
The matrix form records the same program, not a simpler one. Converting to it neither removes constraints nor changes the feasible set.

Forms this is expressed in

The same content in several forms. Each makes something visible that the others leave implicit, so moving between them is part of understanding the topic rather than a presentation choice.

symbolic

The product $A x$ read one row at a time. Row $i$ of $A$ is the coefficient vector $a_{i}^{T}$ of constraint $i$ , and the $i$ th entry of $A x$ is the dot product $a_{i}^{T} x$ : the amount of resource $i$ that the plan $x$ consumes. The constraint set is then $m$ separate statements, $a_{i}^{T} x \leq b_{i}$ for $i = 1, \dots, m$ , all required to hold at once.

This form answers questions about a point. Deciding feasibility is running down the rows and comparing each dot product with its right-hand side. Identifying the active set is collecting the rows that hold with equality. Describing the feasible region as an intersection of half-spaces is the same reading applied to every row at once.

What it does not expose is what a plan is made of. A row mixes every variable together into one number, so nothing in this reading isolates the contribution of a single activity, which is what a basis selects and what a pivot exchanges.

Translates into: symbolic

symbolic

The product $A x$ read one column at a time. Column $j$ of $A$ is the vector $A_{j}$ holding everything variable $j$ contributes, one entry per constraint, and the product expands as

A x = x_{1} A_{1} + x_{2} A_{2} + \dots + x_{n} A_{n} .

So $A x$ is a combination of the columns, with the decision variables as the weights. Column $j$ is the resource profile of activity $j$ : run it at level $x_{j}$ and it consumes $x_{j} A_{j}$ .

This form answers questions about which plans are available. A basis is a selection of $m$ independent columns; a basic solution solves $A_{B} x_{B} = b$ using only those; a simplex direction is $u = A_{B}^{- 1} A_{j}$ , built from the entering column; a reduced cost prices one column against the current basis. Every one of those objects is a statement about columns, which is why the method is presented for programs written $A x = b$ .

What it does not expose is whether a given point is allowed. Feasibility is a row question, and no single column answers it.

Translates into: symbolic

Worked material

Non-example

Four assemblies that are not the program

Comparing the vectors as wholes. A reader takes $A x \leq b$ to mean that $A x$ is shorter than $b$ , or that its entries sum to less. With $A x = (95, 80, 185)^{T}$ and $b = (120, 90, 250)^{T}$ both readings happen to agree with the entrywise one, which is why the mistake survives. Take $A x = (135, 90, 225)^{T}$ instead: the total is smaller than the total of $b$ , and the plan is infeasible, because row 1 gives $135 > 120$ . 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 $A x$ 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} \geq 12$ entered as the row $(1, 1, 0)$ with right-hand side $12$ asserts $x_{1} + x_{2} \leq 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.

Contrast

The same matrix, read two ways

Take

A = (\begin{matrix} 2 & 1 & 3 \\ 1 & 2 & 2 \\ 4 & 3 & 5 \end{matrix}), b = (\begin{matrix} 120 \\ 90 \\ 250 \end{matrix}),

for three products and three resources.

	Row reading	Column reading
What one line is	a constraint	an activity
Row 2 / column 2 says	product mix uses $x_{1} + 2 x_{2} + 2 x_{3}$ labour hours, at most $90$	one unit of product 2 uses $1$ machine hour, $2$ labour hours, $3$ kg
The question it answers	is this plan allowed?	what does this product cost in resources?
$A x$ is	a list of resource totals, one per constraint	$x_{1} A_{1} + x_{2} A_{2} + x_{3} A_{3}$
Used by	feasibility, active sets, the polyhedron	bases, pivots, reduced costs

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.

Common errors

Common misconception

In $A x \leq b$ the inequality compares the vectors as wholes, by length, by total, or by some ordering of vectors, rather than asserting that each entry of $A x$ is at most the corresponding entry of $b$ .

The Matrix Form of a Linear Program

Assumptions and scope

Forms this is expressed in

Worked material

Four assemblies that are not the program

The same matrix, read two ways

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history