Fractal orthogonal matrices

Fractal Orthogonal Matrices with Equal Projection

Summary: Equal-projection orthogonal (EPO) matrices are orthogonal matrices where all matrix elements have the same absolute magnitude. It turns out that real-valued equal projection orthogonal matrices of size 2^n, where n>1, can be iteratively composed from elementary 2 x 2 EPO matrices in a fractal manner. More formally, an equal-projection orthogonal matrix of size 2^n can be composed from 4 smaller EPO matrices of size 2^{n-1}. The resulting matrix has a fractal structure in the sense that all consecutive divisions into four parts down to the 2 x 2 size (n=1) also produce EPO matrices.

Orthogonal matrices are an important matrix class in linear algebra . These are square matrices that represent isometric transformations of a Euclidean space – that is, transformations that preserve all angles and distances. Each of the rows (or columns) of an orthogonal matrix is a unit vector, meaning its absolute magnitude is equal to 1, and each of the rows (or columns) is orthogonal to every other row (or column). It’s easy to check whether a matrix is orthogonal – for an orthogonal matrix Q, the product of the matrix with its transpose gives the identity matrix, I :

An interesting subset of orthogonal matrices are equal-projection orthogonal (EPO) matrices, where all matrix elements have the same absolute magnitude and, for real values, differ only in their signs. These matrices encode a basis change in which the new axes project equally onto each of the old axes. If we limit ourselves to real numbers, these matrices can be conveniently thought of as containing only 1 and -1 elements, with a normalizing factor applied to each element to preserve the unit magnitude of columns and rows:

The above EPO matrix is the smallest equal-projection orthogonal matrix (size \textbf{\textit{N}}=2), and is frequently encountered in physical sciences in the context of constructive and destructive combinations. The 1/\sqrt{2} in front of the matrix is the above-mentioned normalizing factor, which in general is equal to 1/\sqrt{\textbf{\textit{N}}} == 1/\sqrt{2^n}. In the following discussion, we’ll drop the normalizing factors for simplicity, but remember that they need to be there for orthonormality. There are actually four different equal-projection 2 x 2 matrices that differ in the location of the -1 element:

In addition, we can obtain four more such orthogonal matrices by reversing the signs of all elements in a, b, c and d. These four additional matrices could be referred to as -a, -b, -c and -d.

Interestingly, we can use these elementary matrices as building blocks to iteratively compose any equal-projection orthogonal matrix of size 2^n, for integer n>1. Here’s how the algorithm works:

  1. Start by picking any of the four 2 x 2 elementary EPO matrices ad (or one of their negatives) as the initial building block. For these matrices, n=1 (2^n=2).
  2. Place four copies of the building block matrix side by side as four quadrants to form a square matrix with sides twice as large as the building blocks (size = 2^{n+1}).
  3. Pick any of the four elementary matrices ad (or one of their negatives) as a template matrix.
  4. Multiply the four quadrants of the 2^n matrix created in step 2 by the corresponding four elements of the template matrix.
  5. The resulting matrix is a size 2^{n+1} EPO matrix. Repeat steps 2-5 with this new matrix as a building block to obtain next larger size EPO matrix, if needed.

In essence, any size 2^n EPO matrix formed by the above algorithm is determined by  a sequence of n choices among the elementary 2 x 2 EPO matrices. This sequence – for instance, {a, c, -b} – uniquely defines the resulting matrix. Let’s demonstrate how this algorithm operates using this particular {a, c, -b} sequence as an example of building an 8 x 8 EPO matrix.

The first element in this sequence, a, determines the initial building block. After laying four a matrices side by side, as specified in Step 2, we obtain the following 4 x 4 matrix:

The next element in the sequence, c, specifies the selection of the template matrix for this iteration. After multiplying the quadrants of the above matrix by the respective elements of c, our we obtain the following 4 x 4 EPO matrix:

The darkened quadrant shows the elements that changed their signs as a result of multiplication, since the element corresponding to that quadrant in the elementary matrix c is equal to -1.

There is one more element in the sequence, -b, so we proceed through one additional iteration to obtain an 8 x 8 EPO matrix. This is the result of concatenating four copies of our current 4 x 4 EPO matrix:

After multiplying the four quadrants by the corresponding elements of -b, the above becomes an 8 x 8 EPO matrix:

As before, the three darkened quadrants denote where the matrix elements changed their signs because of -1‘s in the -b matrix. If the {a, c, -b} sequence were longer, we could continue building larger and larger EPO matrices by iterating through steps 2-5.

If you’d like to experiment with these matrices yourself, here’s a Mathematica file that implements the above algorithm to get you started.