Kronecker Product

The definition

For an m × p matrix A and an n × q matrix B, the Kronecker product A ⊗ B is the mn × pq matrix obtained by replacing each entry aᵢⱼ of A with the block aᵢⱼ·B:

A ⊗ B = [ a₁₁·B   a₁₂·B   ⋯   a₁p·B ]
        [ a₂₁·B   a₂₂·B   ⋯   a₂p·B ]
        [   ⋮       ⋮     ⋱     ⋮   ]
        [ am₁·B   am₂·B   ⋯   amp·B ]

The two matrices need no compatibility — their dimensions multiply rather than match. A 2 × 2 Kronecker a 2 × 2 gives a 4 × 4. A 3 × 5 Kronecker a 4 × 2 gives a 12 × 10.

Worked example — 2×2 Kronecker 2×2

Take

A = [ 1  2 ]      B = [ 0  5 ]
    [ 3  4 ]          [ 6  7 ]

Each entry of A becomes a scaled copy of B in the output 4 × 4 matrix:

A ⊗ B = [ 1·B   2·B ]
        [ 3·B   4·B ]

      = [ [0  5]   [ 0  10] ]
        [ [6  7]   [12  14] ]
        [ [0 15]   [ 0  20] ]
        [ [18 21]  [24  28] ]

  Spelled out:

      = [  0   5   0  10 ]
        [  6   7  12  14 ]
        [  0  15   0  20 ]
        [ 18  21  24  28 ]

Sanity-check the top-left 2 × 2 block: a₁₁ = 1, so the block is 1·B = B. ✓ Top-right block: a₁₂ = 2, so the block is 2·B = [[0, 10], [12, 14]]. ✓ Output dimensions: (2·2) × (2·2) = 4 × 4. ✓

The mixed-product property

The single identity that makes the Kronecker product useful in practice:

(A ⊗ B)(C ⊗ D) = (A·C) ⊗ (B·D)

valid whenever A·C and B·D are themselves defined (matching inner dimensions). The huge mn × pq product on the left factors as the product of two much smaller products on the right. Direct corollaries:

• Inverse. (A ⊗ B)⁻¹ = A⁻¹ ⊗ B⁻¹ when both inverses exist.
• Transpose. (A ⊗ B)ᵀ = Aᵀ ⊗ Bᵀ.
• Power. (A ⊗ B)ᵏ = Aᵏ ⊗ Bᵏ.
• Eigenvalues. If Auᵢ = λᵢuᵢ and Bvⱼ = μⱼvⱼ, then (A ⊗ B)(uᵢ ⊗ vⱼ) = (λᵢμⱼ)(uᵢ ⊗ vⱼ). The spectrum of A ⊗ B is the multiplicative grid {λᵢμⱼ}.
• Determinant and trace. det(A ⊗ B) = det(A)ⁿ · det(B)ᵐ and tr(A ⊗ B) = tr(A) · tr(B).

The vec identity

Let vec(X) denote the column-stacking operator that turns an n × p matrix X into an np-vector by concatenating its columns. The Kronecker product's most important practical identity:

vec(A · X · B) = (Bᵀ ⊗ A) · vec(X)

This turns matrix equations into ordinary linear systems. The Sylvester equation AX + XB = C becomes (Iₙ ⊗ A + Bᵀ ⊗ Iₘ) · vec(X) = vec(C) — a single big linear system in vec(X). The Lyapunov equation AX + XAᵀ = −Q drops out as the special case B = Aᵀ. These show up everywhere in control theory, model reduction, and matrix interpolation.

Variants and related products

• Khatri–Rao product (columnwise Kronecker). For matrices with the same number of columns, A ⊙ B has columns aₖ ⊗ bₖ. Common in canonical polyadic tensor decomposition.
• Hadamard product. Elementwise A ⊙ B for matrices of the same shape. Not a Kronecker variant despite occasionally being confused with one — its dimensions match rather than multiply.
• Tracy–Singh product. Block Kronecker — generalises ⊗ to a fixed block partition. Used in multivariate statistics for nested factor models.
• Tensor product on operators. Abstract version. Where Kronecker gives a specific matrix in a specific basis, the tensor product is the basis-free statement — exactly the relationship between matrix and linear map.
• Direct sum vs Kronecker. Direct sum A ⊕ B is the block-diagonal matrix; Kronecker product A ⊗ B is much larger and has all blocks scaled. Direct sum dimensions add; Kronecker dimensions multiply.

Algorithm — naive Kronecker

function kron(A, B):
    m, p = shape(A)
    n, q = shape(B)
    K = zeros(m*n, p*q)
    for i in 0 .. m-1:
        for j in 0 .. p-1:
            a = A[i][j]
            // Place a·B block at rows [i·n .. i·n + n), cols [j·q .. j·q + q)
            for r in 0 .. n-1:
                for c in 0 .. q-1:
                    K[i*n + r][j*q + c] = a * B[r][c]
    return K

// Faster: never form K explicitly. The vec identity gives
// (B^T ⊗ A) · x = vec(A · reshape(x, n, q) · B)
function kronvec(A, B, x):           // computes (B^T ⊗ A) · x without forming the Kronecker
    n, q = shape(B)
    m, _ = shape(A)
    X = reshape(x, n, q)             // column-major
    Y = A @ X @ B                    // O(mnq + mpq) — much cheaper than O(m² n² p q)
    return vec(Y)

Explicit construction is O(mnpq) memory and time. For matvecs, the kronvec trick reduces work from O(m·n·p·q) (forming the full mn × pq matrix and multiplying) to O(mn(p + q)) — orders of magnitude faster for large factor sizes.

Kronecker vs tensor vs Hadamard vs direct sum

	Kronecker A ⊗ B	Tensor (abstract) V ⊗ W	Hadamard A ⊙ B	Direct sum A ⊕ B
Inputs	m×p, n×q matrices	Vector spaces of any dim	Two matrices of same shape	m×p, n×q matrices
Output shape	mn × pq	dim V · dim W	m × p (same as inputs)	(m+n) × (p+q) block diagonal
Dimension rule	Multiply	Multiply	Unchanged	Add
Mixed product?	Yes: (A⊗B)(C⊗D)=AC⊗BD	Yes (operator tensor)	No — limited algebra	Yes: (A⊕B)(C⊕D)=AC⊕BD
Concrete or abstract	Concrete matrix in basis	Abstract	Concrete elementwise	Concrete block diagonal
Typical use	Quantum states, vec equations, separable PDEs	Multilinear algebra, physics	Elementwise reweighting, attention	Independent subsystems, block solvers

Where the Kronecker product shows up

• Quantum mechanics — composite systems. n qubits form a 2ⁿ-dimensional Hilbert space whose computational basis is the Kronecker product of single-qubit bases. Two-qubit gates like CNOT are 4 × 4 matrices built from Kronecker products of 2 × 2 single-qubit operators with identity matrices acting on the other qubit.
• Separable PDE solvers. The 2D Laplacian on an n × n grid (with separable boundary conditions) factors as Iₙ ⊗ D + D ⊗ Iₙ where D is the 1D Laplacian. Diagonalising D once gives the eigenvectors of the full operator — the basis of the Fast Sine Transform Poisson solver, O(n² log n) vs O(n⁶) direct.
• Sylvester and Lyapunov equations. AX + XB = C in control theory becomes (Iₙ ⊗ A + Bᵀ ⊗ Iₘ) vec(X) = vec(C) via the vec identity. Bartels–Stewart algorithm exploits this structure to solve in O(n³) instead of O(n⁶).
• Image processing — separable filters. A 2D filter is separable when it equals u·vᵀ for vectors u, v — equivalent to having a single nonzero singular value. The 2D convolution then factors via Kronecker products into two 1D convolutions, dropping cost from O(k²N²) to O(kN²).
• Statistics — multivariate models. The covariance of vec(Y) for a matrix-variate normal Y ~ MN(M, U, V) is V ⊗ U — separable across rows and columns. Vec-Kronecker structure makes likelihoods tractable for high-dimensional matrix data.
• Tensor networks and tensor-train decompositions. Compress an order-d tensor with n levels per index from nᵈ entries to O(d·n·r²) by representing it as a chain of Kronecker products with rank-r couplings. Enables high-dimensional quantum simulation and machine-learning models that would otherwise be infeasible.
• Signal processing — DFT matrix factorisation. The fast-Fourier-transform butterfly structure is exactly a recursive Kronecker product: F₂ₙ = (F₂ ⊗ Iₙ) · D · (Iₙ ⊗ Fₙ) · P. This factorisation is the engine that turns O(n²) DFT into O(n log n).

Common mistakes

• Computing A ⊗ B explicitly when you only need (A ⊗ B)x. Forming the full mn × pq matrix wastes memory by a factor of pq. Use the vec/reshape identity x → vec(A · reshape(x, n, q) · B).
• Assuming A ⊗ B = B ⊗ A. The Kronecker product is not commutative in general. They are similar via a permutation matrix (B ⊗ A = P · (A ⊗ B) · Pᵀ for the perfect-shuffle permutation), but their entries are arranged differently.
• Confusing Kronecker with Hadamard. Hadamard is elementwise A ⊙ B for same-shape matrices — its dimensions don't grow. Kronecker is the structural product that multiplies dimensions. They are usually distinguished by ⊗ vs ⊙ but the symbols are easy to misread.
• Forgetting eigenvalue multiplicities. The spectrum {λᵢμⱼ} counts each combination once, but identical products from different (i, j) pairs accumulate. tr(A ⊗ B) = tr(A) · tr(B) only works because it sums over the full grid with no deduplication.
• Misapplying the vec identity row-major vs column-major. vec is column-stacking by convention. If your library stores matrices row-major (e.g. NumPy without explicit Fortran order), apply vec via X.flatten('F') or transpose first. A common source of off-by-block bugs.
• Storing huge Kronecker matrices that should never be formed. The 2D Laplacian on a 1000 × 1000 grid is 10⁶ × 10⁶ as a Kronecker product — a terabyte of memory if formed. Always operate on the factors with the mixed-product or vec identities.