Matrix Multiplication

Overview

Matrix multiplication is the operation that makes matrix algebra more than a bookkeeping convenience, and it is defined by extending the matrix-vector product across the columns of a second matrix. If $A$ is $m \times n$ and $B$ is $n \times p$ with columns $B_1, B_2, \ldots, B_p$ , then $A B$ is the $m \times p$ matrix whose $i$ -th column is $AB_i$ . Each column of the result is an independent linear combination of the columns of $A$ , weighted by one column of $B$ .

Two features distinguish this from the operations defined earlier. It is not entrywise: the entry in position $(i,j)$ of $A B$ depends on an entire row of $A$ and an entire column of $B$ , not on the entries in position $(i,j)$ of the operands. And it is not shape-preserving: the operands may have three different sizes between them, with the inner dimensions required to agree and the outer dimensions determining the result. An entrywise product of same-sized matrices is a perfectly definable operation, but it is not this one and does not have this one's properties.

The definition looks arbitrary until it is read as composition. Applying $B$ to a vector and then applying $A$ to the result is the same as applying the single matrix $A B$ to that vector. Matrix multiplication is therefore the algebraic encoding of doing one linear operation after another, and the inner-dimension rule is simply the requirement that the output of the first stage be an acceptable input to the second. Every property the product has — associativity, distributivity, the failure of commutativity — is a property of composition.

The failure of commutativity is the point at which intuition carried over from scalar arithmetic must be abandoned. For rectangular matrices, reversing the order usually produces an undefined expression or a differently sized result. Even for square matrices of the same size, where both products exist and have the same shape, they generally differ. Nothing may be assumed about matrix products without a theorem, and the theorems that hold are the subject of a separate treatment.

Definition

Let $A$ be an $m \times n$ matrix and $B$ an $n \times p$ matrix with columns $B_1, B_2, B_3, \ldots, B_p$ . The matrix product $A B$ is the $m \times p$ matrix whose $i$ -th column is the matrix-vector product $AB_i$ . Symbolically, $AB = A[\,B_1 \mid B_2 \mid \cdots \mid B_p\,] = [\,AB_1 \mid AB_2 \mid \cdots \mid AB_p\,]$ .

The product is written by juxtaposition. The number of columns of $A$ must equal the number of rows of $B$ ; no other pairing is defined.

Conformability for Multiplication

CFM

Two matrices are conformable for the product $A B$ when the column count of $A$ equals the row count of $B$ . This shared value is the inner dimension and vanishes from the result; the surviving outer dimensions give the size of $A B$ . Writing the sizes adjacently, $(m \times n)(n \times p) \to (m \times p)$ , makes the rule mechanical.

Conformability for $A B$ says nothing about conformability for $B A$ . Both hold only when $p = m$ .

Commuting Matrices

CMM

Square matrices $A$ and $B$ of the same size commute when $AB = BA$ . This is a special property, not a general one. Examples include any matrix with the identity, any matrix with a scalar multiple of itself, any two powers of the same matrix, and any two diagonal matrices; generic pairs do not commute.

The commutator $AB - BA$ measures the failure and is central in control theory and quantum mechanics, where a non-zero commutator has direct physical meaning.

Concepts

Why the definition is what it is

Read $A$ and $B$ as linear operations. Applying $B$ to a vector $\vec{x}$ and then applying $A$ gives $A(B\vec{x})$ , and the composite is itself a linear operation, so it must be represented by some matrix $C$ with $C\vec{x} = A(B\vec{x})$ for all $\vec{x}$ . Setting $\vec{x} = \vec{e}_i$ extracts column $i$ of $C$ on the left and gives $AB_i$ on the right, so $C$ must be exactly the matrix defined above. The definition is not a convention chosen for convenience; it is forced by the requirement that the product represent composition.

The size rule and what it means

The requirement that the inner dimensions agree is the requirement that the output of $B$ be an acceptable input to $A$ . If $B$ maps size- $p$ vectors to size- $n$ vectors and $A$ maps size- $n$ vectors to size- $m$ vectors, the composite maps size- $p$ to size- $m$ , which is precisely the $m \times p$ shape of $A B$ . Checking conformability is therefore not a formality but a check that the operations can be chained at all.

Non-commutativity, in three degrees

The failure of commutativity appears at three levels. For a general rectangular pair, $B A$ is simply undefined: if $A$ is $3 \times 5$ and $B$ is $5 \times 4$ then $A B$ is $3 \times 4$ while $B A$ requires a $4$ to match a $3$ . When both products exist but the matrices are not square, the results have different sizes: $A$ of size $3 \times 5$ and $B$ of size $5 \times 3$ give a $3 \times 3$ product one way and a $5 \times 5$ product the other. And when both are square of the same size, both products exist with the same shape but generally differ entry for entry.

Reading the product by columns and by rows

The definition says each column of $A B$ is a combination of the columns of $A$ , with weights from the corresponding column of $B$ . It follows that every column of $A B$ lies in the column space of $A$ , hence $\mathcal{C}(AB) \subseteq \mathcal{C}(A)$ and $\operatorname{rank}(AB) \le \operatorname{rank}(A)$ . A symmetric argument on rows gives every row of $A B$ as a combination of the rows of $B$ , so $\operatorname{rank}(AB) \le \operatorname{rank}(B)$ as well. Both bounds fall straight out of the column definition and are not obvious from an entrywise formula.

Zero divisors and the loss of cancellation

The product of two non-zero matrices can be the zero matrix — take $A$ with a single $1$ in position $(1,2)$ and $B$ with a single $1$ in position $(1,1)$ , both $2 \times 2$ . Consequently $AB = AC$ does not imply $B = C$ , and $AB = O$ does not imply that $A$ or $B$ is zero. Cancellation, taken for granted in scalar algebra, requires a hypothesis such as non-singularity of $A$ . Assuming it without that hypothesis is one of the most damaging errors in matrix manipulation.

Powers and the meaning of repetition

For a square matrix, $A^k$ denotes $k$ repeated products, which represents applying the same linear operation $k$ times. In a discrete-time state model $\vec{x}_{k+1} = A\vec{x}_k$ , the state after $k$ steps is $A^k\vec{x}_0$ , so the long-run behaviour of the system is the behaviour of the powers — growth, decay or oscillation according to the eigenvalues. Powers are also where non-commutativity bites hardest: $(AB)^2 = ABAB$ cannot be simplified to $A^2B^2$ unless $A$ and $B$ commute.

Procedure: forming the product $A B$

Check the inner dimensionsThe column count of

A

must equal the row count of

B

. If not, the product does not exist — and check whether

B A

was intended instead.

Record the result sizeThe product is

m \times p

, taking the row count of

A

and the column count of

B

. The shared inner dimension disappears.

Take one column of $B$ at a timeColumn

i

of the result is

AB_i

, the linear combination of the columns of

A

weighted by the entries of column

i

B

Assemble the columnsPlace the

p

computed vectors side by side. Each has

m

entries, matching the claimed result size.

Verify with the entry formulaRecompute one or two entries as the weighted sum of a row of

A

against a column of

B

. Disagreement localises the error to a single position.

Equations

Definition of the matrix product

EQ-MM-01

A B = A [B_{1} ∣ B_{2} ∣ \dots ∣ B_{p}] = [A B_{1} ∣ A B_{2} ∣ \dots ∣ A B_{p}]

Each column of the result is the matrix-vector product of $A$ with the corresponding column of $B$ .

Conformability and result size

EQ-MM-02

(m \times n) (n \times p) \to (m \times p)

The inner dimensions must agree and are consumed; the outer dimensions survive as the shape of the product.

The product as composition

EQ-MM-03

(A B) \vec{x} = A (B \vec{x}) \forall \vec{x} \in ℂ^{p}

Applying $B$ then $A$ equals applying $A B$ . This property forces the definition rather than following from it as an afterthought.

Worked product of a $3 \times 3$ with a $3 \times 2$

EQ-MM-04

Worked product of a $3 \times 3$ with a $3 \times 2$

The result is $3 \times 2$ . The reversed product does not exist, since a $3 \times 2$ matrix cannot multiply a $3 \times 3$ one.

Matrix multiplication is not commutative

EQ-MM-05

A = [\begin{matrix} 2 & 1 \\ 0 & 3 \end{matrix}], B = [\begin{matrix} 1 & 4 \\ - 2 & 0 \end{matrix}] \Rightarrow A B = [\begin{matrix} 0 & 8 \\ - 6 & 0 \end{matrix}] \neq [\begin{matrix} 2 & 13 \\ - 4 & - 2 \end{matrix}] = B A

Both products exist and are $2 \times 2$ , yet they disagree in every entry. Order is part of the operation.

Rank bounds from the column and row readings

EQ-MM-06

C (A B) \subseteq C (A), rank (A B) \leq min (rank (A), rank (B))

Every column of the product is a combination of the columns of $A$ , and every row is a combination of the rows of $B$ . Multiplication can destroy rank but never create it.

Zero divisors: non-zero matrices with zero product

EQ-MM-07

Zero divisors: non-zero matrices with zero product

Neither factor is the zero matrix, yet the product is. Cancellation therefore fails without a non-singularity hypothesis.

Variable Definitions

Symbols used on this page
Symbol	Name	Meaning	Domain / type
$A$	Left factor	The $m \times n$ matrix whose columns are combined	M_{mn}
$B$	Right factor	The $n \times p$ matrix supplying the combination coefficients	M_{np}
$B_{i}$	Column of $B$	The $i$ -th column, a vector of size $n$	C^n
$A B$	Matrix product	The $m \times p$ matrix with $i$ -th column $AB_i$	M_{mp}
$m$	Rows of $A$	Becomes the row count of the product	positive integer
$n$	Inner dimension	Columns of $A$ and rows of $B$ ; consumed by the product	positive integer
$p$	Columns of $B$	Becomes the column count of the product	positive integer
$A^{k}$	Matrix power	The square matrix $A$ multiplied by itself $k$ times	n x n matrix
$C (A)$	Column space	Span of the columns of $A$ ; contains every column of $A B$	subspace of C^m

Worked Numerical Example

Problem statement

A signal chain applies a $3 \times 3$ mixing matrix $A$ to a three-channel intermediate signal, which is itself produced from two source presets by a $3 \times 2$ matrix $B$ . Form the single equivalent matrix $A B$ that maps presets directly to outputs, then demonstrate on a square pair that the order of multiplication cannot be reversed.

State the two matrices and check conformability
$A$ is $3 \times 3$ and $B$ is $3 \times 2$ . The inner dimensions are both $3$ , so $A B$ exists and is $3 \times 2$ . The reversed product $B A$ would need a $2$ to match a $3$ and does not exist at all.
$A = [\begin{matrix} 2 & - 1 & 0 \\ 1 & 4 & - 2 \\ 0 & 3 & 5 \end{matrix}], B = [\begin{matrix} 3 & 1 \\ - 2 & 0 \\ 1 & 2 \end{matrix}]$
Compute the first column of the product
Column 1 of $A B$ is $AB_1$ with $B_1 = (3, -2, 1)$ : combine the columns of $A$ with those weights. This gives $3(2,1,0) + (-2)(-1,4,3) + 1(0,-2,5) = (6,3,0) + (2,-8,-6) + (0,-2,5)$ .
$A B_{1} = [\begin{matrix} 8 \\ - 7 \\ - 1 \end{matrix}]$
Compute the second column
Column 2 uses $B_2 = (1, 0, 2)$ . The zero coefficient drops the middle column of $A$ entirely: $1(2,1,0) + 0(-1,4,3) + 2(0,-2,5) = (2,1,0) + (0,-4,10)$ .
$A B_{2} = [\begin{matrix} 2 \\ - 3 \\ 10 \end{matrix}]$
Assemble the product
Place the two computed columns side by side. The result is $3 \times 2$ , mapping the two presets directly to three outputs and eliminating the intermediate stage.
$A B = [\begin{matrix} 8 & 2 \\ - 7 & - 3 \\ - 1 & 10 \end{matrix}]$
Verify one entry independently
Compute $[AB]_{32}$ as the weighted sum of row 3 of $A$ against column 2 of $B$ : $(0)(1) + (3)(0) + (5)(2) = 10$ . This matches, and because it traverses the data differently it is a genuine check on the column computation.
$[A B]_{32} = (0) (1) + (3) (0) + (5) (2) = 10$
Confirm the composition property
Apply $B$ to the preset vector $(1, 1)$ to get the intermediate $(4, -2, 3)$ , then apply $A$ to obtain $(10, -10, 9)$ . Applying the single matrix $A B$ to $(1,1)$ gives $(8+2, -7-3, -1+10) = (10, -10, 9)$ . The two routes agree, as composition requires.
Demonstrate non-commutativity on a square pair
Take two $2 \times 2$ matrices so that both orders are defined and both results are $2 \times 2$ . Computing each entry from the row-column rule gives two entirely different matrices, so the order of a matrix product carries real information.
$Demonstrate non-commutativity on a square pair$

Result

The single matrix $A B$ replaces the two-stage chain exactly, so the intermediate signal need never be formed at runtime — a saving of one full pass over the data per sample, paid for once at configuration time. The square example shows why the order in which stages are collapsed cannot be permuted: swapping the two matrices changes every output. In a signal chain this is the formal statement that filtering then mixing is a different system from mixing then filtering.

Applications & Industry Use

Computer graphics

Collapsing a transformation chain

Model, view and projection transformations are applied in sequence to every vertex. Multiplying the three matrices once per frame and applying the single result to millions of vertices replaces three matrix-vector products per vertex with one. The order of the product is fixed by the order of the transformations and cannot be permuted.

Robotics

Forward kinematics by chained frames

The pose of an end effector is the product of homogeneous transformation matrices, one per joint, taken in link order. Non-commutativity is physically visible: rotating about one axis then another does not place the tool where the reverse order would.

Control systems

State transition over multiple steps

For a discrete-time model $\vec{x}_{k+1} = A\vec{x}_k$ , the state after $k$ samples is $A^k\vec{x}_0$ . Stability, settling and oscillation are read from the behaviour of the powers, and controllability matrices are built from products $[\,B \mid AB \mid A^2B \mid \cdots\,]$ .

Machine learning

Batched layer evaluation

Evaluating a dense layer on a batch of samples is a matrix-matrix product rather than many matrix-vector products. This reuses each weight across the whole batch, moving the workload from memory-bound to compute-bound and delivering most of the throughput advantage of accelerator hardware.

Structural engineering

Assembling element stiffness in global coordinates

An element stiffness matrix expressed in local coordinates becomes $T^{t}KT$ in global coordinates, a triple product with the rotation matrix $T$ . The order is dictated by which frame each factor acts in, and reversing it silently produces a wrong but plausible stiffness.

Operations research

Multi-stage transition and flow models

A Markov chain's $k$ -step transition probabilities are the entries of $P^k$ . Similarly, chaining a supply matrix with a demand allocation matrix gives end-to-end flow in one operation, with the inner dimension being the intermediate stage that the product eliminates.

Design Considerations

Choose the multiplication order to minimise work

Associativity permits regrouping a chain of products, and the cost depends dramatically on the grouping. For $A$ of size $1000 \times 5$ , $B$ of size $5 \times 1000$ and $\vec{x}$ of size $1000$ , computing $A(B\vec{x})$ costs about $20{,}000$ operations while $(AB)\vec{x}$ costs about $12$ million. Always contract against the vector first, and for longer chains solve the matrix chain ordering problem before executing.

Never form a product you only apply

If a chain of matrices is applied to a handful of vectors, apply the factors in turn rather than materialising the product. Forming $A B$ costs $2mnp$ operations and $m p$ storage, both of which are wasted when the composite is used once. Materialise only when the composite will be reused many times or when a factorisation of it is required.

Treat order as semantically load-bearing

Because the product is not commutative, the order in an expression records the order of physical operations. Reversing a factor pair in code produces a result of the correct shape and entirely wrong meaning, which no dimension check will catch. Encode the order in naming conventions and validate against a case where the two orders demonstrably differ.

Do not assume cancellation

From $AB = AC$ it does not follow that $B = C$ , and from $AB = O$ it does not follow that either factor is zero. Cancellation requires $A$ to be non-singular, in which case multiplying by $A^{-1}$ on the left justifies it. Any manipulation that divides through by a matrix must first establish invertibility, and must respect the side on which the inverse is applied.

Exploit structure before optimising the general kernel

A product involving a diagonal matrix is a row or column scaling costing $O(mn)$ , not $O(mnp)$ . A triangular, banded, orthogonal or low-rank factor similarly admits a much cheaper product. Recognising that a matrix is a permutation, a rotation or a rank-one update converts a cubic operation into a linear or quadratic one, which dwarfs any gain from tuning the dense algorithm.

Understand where the cost actually goes

The direct algorithm costs $2mnp$ operations while reading $mn + np$ entries, so unlike matrix-vector work it has high arithmetic intensity and can approach hardware peak. Achieving that requires blocking for cache and registers, which is exactly what tuned xGEMM implementations do. A naive triple loop typically reaches a small percentage of peak, so calling the library is not merely convenient but a large factor in performance.

Standards & Codes

Notation, interchange and numerical standards that govern how this material is written down, stored and computed in production systems.

Applicable standards, conventions and reference implementations
Reference	Title	Relevance to this topic
`BLAS Level 3`	Basic Linear Algebra Subprograms, matrix-matrix operations	The `xGEMM` routine defines the reference interface, including transpose flags and the scaling parameters that make $\alpha AB + \beta C$ a single call; it is the kernel around which dense linear algebra performance is organised.
`ISO 80000-2`	Quantities and units — Part 2: Mathematics	Fixes juxtaposition as the notation for the matrix product and the row-then-column index convention that determines which dimension is the inner one.
`IEEE 754-2019`	IEEE Standard for Floating-Point Arithmetic	Governs the accumulation inside each entry of the product; the fused multiply-add operation defined here is what allows tuned kernels to halve the rounding error while doubling throughput.
`ISO/IEC 14882`	Programming languages — C++	Constrains the reassociation of the accumulation a conforming compiler may perform, and specifies the parallel execution policies used to distribute a product across cores.
`ISO/IEC 40314`	Mathematical Markup Language (MathML) Version 3.0	Encodes juxtaposed matrix products with an explicit invisible-times operator, so the distinction between a product and adjacent unrelated symbols survives into assistive technology.

Material Selection

For a mathematical topic, "material" is the numeric representation: the scalar field, storage format and precision the computation is built from.

Representation and precision selection
Representation	Select when	Trade-off
Dense binary64 with blocked GEMM	General-purpose scientific computation where accuracy is the priority and matrices fit in memory.	Approaches hardware peak with a tuned kernel; 8 bytes per entry and $2mnp$ operations set a hard limit around a few tens of thousands per dimension.
Dense binary32 or reduced precision	Deep learning inference and training, and graphics pipelines.	Two to eight times the throughput on accelerator hardware; error grows with the inner dimension, so mixed-precision accumulation in a wider format is standard practice.
Sparse times dense	One factor comes from a mesh, network or graph with few non-zeros per row.	Cost proportional to non-zeros rather than to $m n p$ ; the product generally suffers fill-in, and irregular access prevents the kernel from reaching peak.
Structured factors (diagonal, permutation, orthogonal)	One factor is a scaling, a reordering or a rotation.	Reduces the product to $O(mn)$ work with no floating-point error in the permutation case; requires the structure to be recognised and preserved rather than assembled into a dense array.
Low-rank factored form	A large operator is well approximated by rank $k \ll \min(m,n)$ , as in compressed models and hierarchical matrices.	Cost drops from $O(mnp)$ to $O(k(m+n+p))$ ; introduces an approximation error and complicates further algebraic manipulation.
Integer or fixed-point arithmetic	Combinatorial products such as adjacency powers, or quantised inference on embedded targets.	Exact for combinatorial work and very fast on quantised hardware; the accumulator must be wide enough for the inner dimension or results overflow silently.

Manufacturing Notes

Implementation notes — how the result is actually produced by hand, by algorithm and by library, including cost and numerical behaviour.

Operation count and arithmetic intensity

The direct algorithm performs $m n p$ multiplications and $mp(n-1)$ additions, about $2mnp$ operations, while reading $mn + np$ entries and writing $m p$ . For square matrices this is $O(n^3)$ arithmetic against $O(n^2)$ data, an intensity proportional to $n$ . That is why matrix multiplication, unlike matrix-vector work, can reach hardware peak — and why almost all dense linear algebra is reorganised to spend its time here.

Hand procedure

Work one column of $B$ at a time and use the column-combination form: the coefficients are read from a single column and stay in view, and each partial result is a full-height vector. Verify by recomputing two or three entries with the row-against-column rule, choosing entries in different rows and columns so that a systematic error cannot hide.

Blocking, and why the library beats a triple loop

A naive triple loop reuses each operand entry $O(1)$ times from cache and typically achieves a few percent of peak. Tiling the computation so that sub-blocks of $A$ , $B$ and the accumulator reside in cache and registers raises reuse to the block size and recovers most of the peak. Tuned xGEMM implementations perform several levels of such blocking together with explicit vectorisation and prefetching.

Sub-cubic algorithms in practice

Strassen's method reduces the exponent from $3$ to about $2.807$ by trading one multiplication for several additions in a recursive $2 \times 2$ block decomposition, and becomes competitive for square matrices of a few thousand and above. It is numerically less stable than the direct algorithm, with a weaker componentwise error bound, and is therefore used selectively. Algorithms with better asymptotic exponents have constants far too large for practical sizes.

Verification techniques

For large products, a full recomputation is unaffordable. Freivalds' method checks $AB = C$ probabilistically by drawing a random vector $\vec{r}$ and comparing $A(B\vec{r})$ against $C\vec{r}$ , costing $O(n^2)$ per trial with an error probability halving each time. Cheap deterministic checks include comparing row sums, since $A B$ applied to the all-ones vector must equal $A$ applied to the row sums of $B$ .

Failure Modes & Common Mistakes

Failure modes, root causes and prevention
Failure mode / mistake	Impact	Root cause	Prevention & detection
Reversing the order of the factors	high	Assuming commutativity, or transcribing a composition in the order the operations are performed rather than the order they are written.	Remember that $A$ acts last in $A B$ . Validate against a case where both orders are defined and demonstrably differ; a shape check alone will not catch this for square matrices.
Non-conformable product	high	The column count of the left factor does not match the row count of the right factor, often after an unintended transpose.	Write the sizes adjacently as $(m \times n)(n \times p)$ and confirm the inner values agree before computing. If they do not, check whether the other order was intended.
Assuming the product is entrywise	high	Generalising from addition and scalar multiplication, so `A * B` is used where `A @ B` is meant.	Check the result shape and one entry: the matrix product entry $(i,j)$ depends on a whole row and a whole column, whereas the entrywise product depends only on position $(i,j)$ .
Cancelling a common factor	high	Deducing $B = C$ from $AB = AC$ without establishing that $A$ is non-singular.	Justify cancellation by explicitly multiplying by $A^{-1}$ , and note the side: left-multiplying by $A^{-1}$ cancels a left factor only.
Materialising a product that is applied once	medium	Forming $A B$ and then computing $(AB)\vec{x}$ instead of $A(B\vec{x})$ .	Contract against the vector first. For longer chains, choose the parenthesisation that minimises the total operation count before executing anything.
Assuming $(AB)^k = A^kB^k$	medium	Carrying scalar exponent rules into a non-commutative setting.	Expand the power explicitly: $(AB)^2 = ABAB$ , which equals $A^2B^2$ only when $A$ and $B$ commute. Verify commutation before applying any such simplification.
Accumulator overflow in integer or fixed-point products	medium	Summing $n$ products in an accumulator no wider than the operands, so a long inner dimension overflows silently.	Size the accumulator for the worst-case sum over the inner dimension, or rescale the operands; quantised inference kernels use a wider accumulator precisely for this reason.
Naive triple loop on large matrices	low	Hand-written multiplication with no blocking, achieving a few percent of hardware peak.	Call a tuned `xGEMM`. The gap between a naive loop and a blocked implementation is typically one to two orders of magnitude and grows with matrix size.

FAQs

Why is matrix multiplication not defined entrywise?

Because the entrywise product does not represent composition of linear operations. The defining requirement is that applying $B$ and then $A$ should be the same as applying a single matrix, and that requirement forces the column-combination definition uniquely. The entrywise (Hadamard) product is a legitimate operation with its own uses, but it does not compose transformations and lacks the associativity structure that makes matrix algebra useful.

When do two matrices commute?

Rarely, and only in identifiable situations: any matrix commutes with the identity, with scalar multiples of itself, and with its own powers; diagonal matrices commute with one another; and simultaneously diagonalisable matrices commute. For a generic pair of square matrices, $A B$ and $B A$ differ in most entries. The commutator $AB - BA$ quantifies the difference and has direct physical meaning in quantum mechanics and Lie theory.

Can

A B

be defined when

B A

is not?

Yes, and this is the usual situation for rectangular matrices. If $A$ is $3 \times 5$ and $B$ is $5 \times 4$ then $A B$ is $3 \times 4$ , but $B A$ requires the column count $4$ of $B$ to match the row count $3$ of $A$ , which fails. Both products exist only when $A$ is $m \times n$ and $B$ is $n \times m$ , and even then they have different sizes unless $m = n$ .

Does

AB = O

mean one of the factors is zero?

No. Matrices form a ring with zero divisors, so two non-zero matrices can multiply to give the zero matrix. Structurally this happens exactly when the column space of $B$ lies inside the null space of $A$ . The consequence for algebraic manipulation is that cancellation is invalid without a non-singularity hypothesis.

How should I order a chain of matrix multiplications?

By operation count, which associativity leaves free to choose. Contracting against a vector first is almost always right, and for a chain of matrices the optimal parenthesisation is found by a short dynamic program on the dimensions. The difference between a good and a bad grouping can be several orders of magnitude for matrices with very different shapes.

Is a faster-than-cubic algorithm worth using?

Sometimes. Strassen's method reduces the exponent to about $2.807$ and becomes competitive for square matrices from roughly a few thousand upward, at the cost of a weaker error bound and extra working memory. Algorithms with better asymptotic exponents carry constants so large that they are of theoretical interest only. For most work, a well-blocked cubic kernel is the right choice.

Why does the same product cost so differently depending on how it is coded?

Because the operation has enough arithmetic per byte to be compute-bound, but only if the data is reused from cache and registers. A naive triple loop reuses almost nothing and stalls on memory; a blocked implementation reuses each loaded block many times and approaches hardware peak. The resulting gap is typically one to two orders of magnitude, which is why the tuned library kernel is worth calling.

References

Beezer, R. A. A First Course in Linear Algebra, Version 0.70. University of Puget Sound, 2006. Section MM, Subsection MM, Definition MM. Licensed under the GNU Free Documentation License v1.2.
ISO 80000-2:2019, Quantities and units — Part 2: Mathematics. International Organization for Standardization.
Golub, G. H. and Van Loan, C. F. Matrix Computations, 4th edition. Johns Hopkins University Press, 2013.
Strassen, V. Gaussian Elimination is Not Optimal. Numerische Mathematik, 13, 1969.
Goto, K. and van de Geijn, R. A. Anatomy of High-Performance Matrix Multiplication. ACM Transactions on Mathematical Software, 34(3), 2008.

AI Suggested Questions

Find two 3x3 matrices that commute but are not diagonal, and explain what structure makes them commute.
Work through the matrix chain ordering problem for four matrices with dimensions 40x20, 20x300, 300x10 and 10x5.
Show me two non-zero 3x3 matrices whose product is the zero matrix, and describe the subspace relationship that causes it.
At what matrix size does Strassen's algorithm start to beat a blocked cubic kernel on typical hardware, and what accuracy do you give up?
Explain why rotating about the x-axis then the y-axis differs from the reverse, using the matrix product to make the difference explicit.
How does Freivalds' algorithm verify a matrix product in quadratic time, and what is the failure probability after five trials?

Related Calculators

Matrix Multiplication Calculator

Multiply two matrices with a conformability check and a column-by-column trace of the computation.

Commutator Calculator

Compute $A B$ , $B A$ and the commutator $AB - BA$ for square matrices, and report whether the pair commutes.

Matrix Chain Order Optimiser

Given a chain of matrix dimensions, return the parenthesisation minimising the total operation count.

Overview

Definition