An application of Kronecker products

A while back I wrote about Kronecker products in the context of higher order Taylor series. Here’s how I described the Kronecker product in that post.

The Kronecker product of an m × n matrix A and a p × q matrix B is a mp × nq matrix K = A ⊗ B. You can think of K as a block partitioned matrix. The ij block of K is a_ij B. In other words, to form K, take each element of A and replace it with its product with the matrix B.

The post gives the example that if

and

then

That post used Kronecker products to express Taylor series for functions of several variables. This post will present another application of Kronecker products.

Hadamard matrices

Hadamard matrices come up frequently in coding theory. For example, the existence of certain codes depends on the existence of Hadamard matrices of a certain size. These matrices also come up in the design of experiments. See Nick Higham’s recent article for applications to numerical linear algebra.

It’s important in application to know when Hadamard matrices exist and to be able to construct them. And the simplest way to construct Hadamard matrices is by taking Kronecker products of smaller Hadamard matrices.

A Hadamard matrix is an orthogonal matrix whose entries are all either +1 or -1. For example, the following is a 2 by 2 Hadamard matrix:

    +1  +1
    +1  -1

Now there’s a theorem due to James Sylvester (1814–1897) that says the Kronecker product of two Hadamard matrices is another Hadamard matrix. So if we can find Hadamard matrices of order p and order q, we can take their Kronecker product to form a Hadamard matrix of order pq. In particular, we can take the Kronecker product of the matrix above with itself n times to form a Hadamard matrix of order 2ⁿ.

So, for example, taking the product once we get a matrix of order 4.

    +1  +1  +1  +1
    +1  -1  +1  -1
    +1  +1  -1  -1
    +1  -1  -1  +1

And taking the product once again we get a Hadamard matrix of order 8.

    +1  +1  +1  +1  +1  +1  +1  +1 
    +1  -1  +1  -1  +1  -1  +1  -1 
    +1  +1  -1  -1  +1  +1  -1  -1 
    +1  -1  -1  +1  +1  -1  -1  +1
    +1  +1  +1  +1  -1  -1  -1  -1 
    +1  -1  +1  -1  -1  +1  -1  +1 
    +1  +1  -1  -1  -1  -1  +1  +1 
    +1  -1  -1  +1  -1  +1  +1  -1

It’s not known for which n there exists a Hadamard matrix of order n, but the construction above shows that there exist Hadamard matrix of every order that’s a power of 2. If n > 2 then a necessary condition for the existence of a Hadamard matrix is that n is a multiple of 4. It is conjectured that this condition is also sufficient. At the time of writing, the smallest multiple of 4 for which no one has found a Hadamard matrix is 668.

Note that, for example, there are Hadamard matrices of order 20, but you cannot find one by multiplying Hadamard matrices of order 4 and 5, because there are no Hadamard matrices of order 5. So if you wanted to create a list of Hadamard matrices of various orders, Sylvester’s theorem would let you quickly fill in some entries, but then things would get much harder.

More linear algebra posts

• Iterative linear solvers
• Linear algebra in infinite dimensions
• SVD and pseudoinverse