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 KA B. You can think of K as a block partitioned matrix. The ij block of K is aij 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

A = \left\[ \begin{array}{cc} 1 & 2 \\ 3 & 4 \\ 5 & 6 \\ 7 & 8 \end{array} \right]

and

B= \left\[ \begin{array}{ccc} 10 & 0 & 0 \\ 0 & 20 & 0 \\ 0 & 0 & 30 \end{array} \right]

then

A \otimes B= \left\[ \begin{array}{cccccc} 10 & 0 & 0 & 20 & 0 & 0 \\ 0 & 20 & 0 & 0 & 40 & 0 \\ 0 & 0 & 30 & 0 & 0 & 60 \\ 30 & 0 & 0 & 40 & 0 & 0 \\ 0 & 60 & 0 & 0 & 80 & 0 \\ 0 & 0 & 90 & 0 & 0 & 120 \\ 50 & 0 & 0 & 60 & 0 & 0 \\ 0 & 100 & 0 & 0 & 120 & 0 \\ 0 & 0 & 150 & 0 & 0 & 180 \\ 70 & 0 & 0 & 80 & 0 & 0 \\ 0 & 140 & 0 & 0 & 160 & 0 \\ 0 & 0 & 210 & 0 & 0 & 240 \\ \end{array} \right]

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 2n.

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

One thought on “An application of Kronecker products

  1. Wow! Hadamard matrices are orthogonal two-level designs! Plackett-Burman designs are special cases! We can generate big designs with Kronecker products! I am SO stealing this.

    This post came just a bit too late to get folded into my senior DOE course, but next spring, ah next spring, my students will get a serious dunk in the deep end of the linear algebra pool. That way, when they study multiply-multivariate repeated measures in grad school, they’ll get it: “So that’s what Old Anderson was talking about with Kronecker products.”

Leave a Reply

Your email address will not be published.