Matrices primer
Matrices Primer
A matrix is a rectangular array of numbers.
An $m \times n$ matrix has:
- $m$ rows
- $n$ columns
A general matrix is written as:
\[A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}\]The entry $a_{ij}$ is the entry in row $i$ and column $j$.
Matrix Size
If $A$ has $m$ rows and $n$ columns, then:
\[A \in \mathbb{R}^{m \times n}\]This means $A$ is a real $m \times n$ matrix.
Example:
\[A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}\]has $2$ rows and $3$ columns, so:
\[A \in \mathbb{R}^{2 \times 3}\]Rows and Columns
For:
\[A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}\]the $i$-th row is:
\[A_i = (a_{i1}, a_{i2}, \ldots, a_{in})\]the $j$-th column is:
\[A_j = \begin{bmatrix} a_{1j} \\ a_{2j} \\ \vdots \\ a_{mj} \end{bmatrix}\]In linear programming, columns of $A$ are especially important because basis matrices are built by selecting columns of $A$.
Matrix as a Table
A matrix can be interpreted as a table.
Example:
| Supplier | Good 1 | Good 2 | Good 3 |
|---|---|---|---|
| Supplier A | 4 | 8 | 3 |
| Supplier B | 5 | 7 | 2 |
This can be represented as:
\[P = \begin{bmatrix} 4 & 8 & 3 \\ 5 & 7 & 2 \end{bmatrix}\]Here $p_{ij}$ is the price of good $j$ from supplier $i$.
Square Matrix
A matrix is square if it has the same number of rows and columns.
An $n \times n$ matrix is called a square matrix of order $n$.
Example:
\[A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\]is a $2 \times 2$ square matrix.
Row Vector and Column Vector
A row vector is a $1 \times n$ matrix:
\[x^T = [x_1, x_2, \ldots, x_n]\]A column vector is an $n \times 1$ matrix:
\[x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}\]In OR, decision variables are usually written as column vectors.
Zero Matrix
The zero matrix has all entries equal to zero.
Example:
\[0 = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}\]Identity Matrix
The identity matrix is a square matrix with:
- $1$ on the diagonal
- $0$ outside the diagonal
Example:
\[I = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\]The identity matrix satisfies:
\[Ix = x\]for any vector $x$ of compatible size.
Matrix Equality
Two matrices $A$ and $B$ are equal if:
- they have the same size
- all corresponding entries are equal
So:
\[A = B\]means:
\[a_{ij} = b_{ij}\]for every row $i$ and column $j$.
Matrix Addition
Matrices of the same size can be added entry by entry.
If:
\[A = (a_{ij}), \qquad B = (b_{ij})\]then:
\[A + B = (a_{ij} + b_{ij})\]Example:
\[\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} + \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix} = \begin{bmatrix} 6 & 8 \\ 10 & 12 \end{bmatrix}\]Scalar Multiplication
A matrix can be multiplied by a scalar.
If:
\[A = (a_{ij})\]then:
\[\alpha A = (\alpha a_{ij})\]Example:
\[3 \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} = \begin{bmatrix} 3 & 6 \\ 9 & 12 \end{bmatrix}\]Transpose
The transpose of a matrix switches rows and columns.
If:
\[A = (a_{ij})\]then:
\[A^T = (a_{ji})\]Example:
\[A = \begin{bmatrix} 0 & 2 & 1 \\ 3 & 7 & 2 \end{bmatrix}\]Then:
\[A^T = \begin{bmatrix} 0 & 3 \\ 2 & 7 \\ 1 & 2 \end{bmatrix}\]Symmetric Matrix
A matrix is symmetric if:
\[A = A^T\]A symmetric matrix must be square.
Example:
\[A = \begin{bmatrix} 2 & 5 \\ 5 & 3 \end{bmatrix}\]is symmetric.
Matrix-Vector Multiplication
If:
\[A \in \mathbb{R}^{m \times n}\]and:
\[x \in \mathbb{R}^n\]then:
\[Ax \in \mathbb{R}^m\]The result is a vector with $m$ entries.
Each entry is the inner product of one row of $A$ with $x$.
If:
\[A = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ a_{31} & a_{32} \end{bmatrix}\]and:
\[x = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\]then:
\[Ax = \begin{bmatrix} a_{11}x_1 + a_{12}x_2 \\ a_{21}x_1 + a_{22}x_2 \\ a_{31}x_1 + a_{32}x_2 \end{bmatrix}\]Matrix-Vector Product in OR
Suppose:
\[A = \begin{bmatrix} 2 & 3 \\ 5 & 1 \end{bmatrix}\]and:
\[x = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\]Then:
\[Ax = \begin{bmatrix} 2x_1 + 3x_2 \\ 5x_1 + x_2 \end{bmatrix}\]So the matrix equation:
\[Ax \le b\]represents multiple constraints at once.
For example:
\[Ax \le \begin{bmatrix} 30 \\ 40 \end{bmatrix}\]means:
\[2x_1 + 3x_2 \le 30\] \[5x_1 + x_2 \le 40\]Constraint Matrix
In linear programming, $A$ is called the constraint matrix.
For the constraints:
\[2x_1 + 3x_2 \le 30\] \[5x_1 + x_2 \le 40\]we write:
\[A = \begin{bmatrix} 2 & 3 \\ 5 & 1 \end{bmatrix}, \qquad x = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}, \qquad b = \begin{bmatrix} 30 \\ 40 \end{bmatrix}\]Then the constraints become:
\[Ax \le b\]Standard Form
A linear programming problem in standard form is:
\[\min c^T x\]subject to:
\[Ax = b\] \[x \ge 0\]Here:
- $A$ is the constraint matrix
- $x$ is the decision variable vector
- $b$ is the right-hand side vector
- $c$ is the cost vector
Matrix Form Example
Consider:
\[\min 4x_1 + 7x_2 + 2x_3\]subject to:
\[x_1 + 2x_2 + x_3 = 10\] \[3x_1 + x_2 + 4x_3 = 20\] \[x_1,x_2,x_3 \ge 0\]Then:
\[c = \begin{bmatrix} 4 \\ 7 \\ 2 \end{bmatrix}\] \[A = \begin{bmatrix} 1 & 2 & 1 \\ 3 & 1 & 4 \end{bmatrix}\] \[b = \begin{bmatrix} 10 \\ 20 \end{bmatrix}\]and the problem is:
\[\min c^T x\]subject to:
\[Ax = b, \qquad x \ge 0\]Matrix Multiplication
If:
\[A \in \mathbb{R}^{m \times n}\]and:
\[B \in \mathbb{R}^{n \times p}\]then:
\[AB \in \mathbb{R}^{m \times p}\]The entry in row $i$, column $j$ of $AB$ is:
\[(AB)_{ij} = \sum_{k=1}^n a_{ik}b_{kj}\]Matrix multiplication is defined only when the number of columns of $A$ equals the number of rows of $B$.
Inverse Matrix
A square matrix $B$ is invertible if there exists a matrix $B^{-1}$ such that:
\[B^{-1}B = I\]and:
\[BB^{-1} = I\]In simplex, basis matrices must be invertible.
This is why the selected columns of $A$ must be linearly independent.
Solving a Linear System
If:
\[Bx = b\]and $B$ is invertible, then:
\[x = B^{-1}b\]This is central in standard-form linear programming.
If $B$ is a basis matrix, the corresponding basic variables are:
\[x_B = B^{-1}b\]Basis Matrix
In a standard-form LP:
\[Ax = b, \qquad x \ge 0\]where:
\[A \in \mathbb{R}^{m \times n}\]a basis matrix $B$ is formed by selecting $m$ linearly independent columns of $A$.
If those columns are:
\[A_{B(1)}, A_{B(2)}, \ldots, A_{B(m)}\]then:
\[B = [A_{B(1)} \ A_{B(2)} \ \cdots \ A_{B(m)}]\]The basic variables are computed from:
\[x_B = B^{-1}b\]Sparse Matrices
A sparse matrix has many zero entries.
Example:
\[A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 5 \end{bmatrix}\]The number of nonzero entries is written:
\[nnz(A)\]Sparse matrices matter because real optimization problems can have thousands or millions of variables and constraints, but most coefficients are zero.
Why Matrices Matter in Simplex
The simplex method repeatedly works with:
\[Ax = b\]and selected basis matrices $B$.
At each step, it computes:
\[x_B = B^{-1}b\]and uses matrix products to decide:
- whether the current solution is feasible
- whether it is optimal
- which variable should enter the basis
- which variable should leave the basis
Checklist
You understand matrices if you can:
- identify the size of a matrix
- identify rows and columns
- add matrices of the same size
- multiply a matrix by a scalar
- compute a transpose
- compute a matrix-vector product
- write constraints as $Ax \le b$ or $Ax=b$
- recognize the identity matrix
- understand what a basis matrix is
- explain why invertibility matters in simplex
See Also
- Vectors
- Linear Systems
- Rank and Linear Independence
- Bases and Invertible Matrices
- Matrix Form of LP Problems
- Standard Form
- Simplex Method
Exam checkpoint
Use this topic only as much as needed to support LP algebra: matrices, rank, bases, linear systems, half-spaces, and hyperplanes. Connect every computation back to $Ax=b$, basis matrices, and feasible regions.