I recently posted an article about self-similar structures that arise in Pascal's triangle. Did you know that the Kronecker product (or direct product) can be used to create matrices that have self-similar structure?

The basic idea is to start with a 0/1 matrix and compute a sequence of direct products of the matrix with itself. If **M** is a matrix that contains only zeros and ones, then **M**@**M** is a block matrix where a block of zeros occurs where **M** has a 0, and a copy of **M** appears where **M** has a 1, as shown by the following SAS/IML program:

proc iml; M = {0 1 0, 1 1 1, 0 1 0}; M2 = M @ M; print M2; |

In this example, the original matrix, **M**, is 3 x 3.
The matrix **M**@**M** is a 3 x 3 block matrix, where each block is either the zero matrix or a copy of **M**. If you apply the Kronecker product again and form the matrix **M**@**M**@**M**, you will get a 9 x 9 block matrix, where each block is either the zero matrix or a copy of **M**.

You can continue this process. The *k*-fold product of **M** with itself is a 3^{k} x 3^{k} matrix.
Arthur Charpentier provides a nice animation of this iterative process on his Freakonometrics blog, which is where I first read about using the Kronecker product of a 0/1 matrix to create a self-similar structure. If you like to read articles about
mathematical aspects of probability and statistics, I highly recommend Charpentier's well-written and always interesting blog.

Printing a 0/1 matrix is not an effective visualization. Instead, I will create a two-color heat map by using the HEATMAPDISC subroutine in SAS/IML 13.1. Because I want to create several heat maps, I wrote the following SAS/IML module that composes a matrix with itself *k* times and draws a two-color heat map of the result. The following heat map shows the structure of the four-fold Kronecker product
**M**@**M**@**M**@**M**:

start KroneckerPlot(M, Iters); N = 1; do i = 1 to Iters; N = N @ M; end; call heatmapdisc(N) title="Iteration: "+strip(char(Iters)) colorramp={White Blue} displayoutlines=0 ShowLegend=0; finish; ods graphics / width=800px height=800px; run KroneckerPlot(M, 4); |

Let's say it all together: "Ooooooh!" "Ahhhhh!"

The structures that you can create depend on the arrangement of zeros and ones in the original matrix. Notice that these product matrices get big fast: the *k*-fold Kronecker product of an *n* x *n* matrix is an *n*^{k} x *n*^{k} matrix. You might run out of memory if you try to visualize a *k*-fold product when *k* or *n* is greater than 5. The next statements start with a 4 x 4 matrix and display a heat map for the five-fold product, which is a 1024 x 1024 matrix:

M = {1 1 1 1, 1 1 0 0, 1 0 1 0, 1 0 0 1}; run KroneckerPlot(M, 5); /* 5 iterations of 4x4 matrix ==> 1024 x 1024 matrix */ |

I call this image "Landing at LaGuardia."

Obviously you can create other structures. You can even generate random structures by using the Bernoulli distribution to create a random 0/1 matrix. I leave you with a few additional statements that create self-similar images. Feel free to create your own matrices. Leave a comment and tell me your favorite matrix for creating a self-similar structure.

ods graphics / width=500px height=500px; M = {1 1 1 1, 1 0 0 1, 1 0 0 1, 1 1 1 1}; run KroneckerPlot(M, 4); /* Make random fractal plots! */ call randseed(54321); do i = 1 to 5; M = randfun({4 4}, "Bernoulli", 0.75); run KroneckerPlot(M, 3); end; |