This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English version of the page.

Magic Squares, Part 3, Linear Algebra 4

Posted by Cleve Moler,

 
We know a little bit, but not much, about the linear algebraic properties of magic squares.

Contents

Rank

Here is my favorite experiment involving the linear algebraic properties of magic squares. Recall that the rank of a matrix is the number of linearly independent rows or columns. If an n -by- n matrix has full rank, that is rank equal to n, then it is nonsingular and has an inverse. Let's look at the rank of the magic squares generated by MATLAB.
    r = zeros(1,33);
    for n = 3:33
       r(n) = rank(magic(n));
    end
    bar(r)
    xlabel('n')
    ylabel('rank')
    title('rank(magic(n))')
    snapnow
We can clearly see three different cases. Odd order magic squares have full rank, singly even order magic squares have rank equal to roughly half their order, and doubly even order magic squares of any order have rank equal to three. Why is that? It reflects the three different cases in the MATLAB magic square generator.

Odd Order

Recall from last week that we have two different ways of generating the odd order magic square produced by magic(n). De La Loubere's method generates the matrix elements one-by-one along broken diagonals in a manner that seems very unlikely to generate linear dependence between rows or columns. Our new algorithm generates the same magic square with a few array operations.
   [I,J] = ndgrid(1:n);
   A = mod(I+J+(n-3)/2,n);
   B = mod(I+2*J-2,n);
   M = n*A + B + 1;
It is not hard to prove that A and B have full rank and so it is likely that their sum has full rank as well. There are many other magic squares besides the ones generated by MATLAB. Are all the odd ordered ones nonsingular? Frankly, I have no idea. The magic square property tells us very little about linear independence. Does anybody know of a 5-by-5 magic square that is also a singular matrix? I would love to see it. Or, can anybody prove that odd-ordered magic squares must be nonsingular? I would love to see a proof as well. Actually, I better see just one or the other.

Doubly Even Order

For doubly even order, the rank is always three. When I first saw that -- years ago -- I was really surprised. For a long time I had a vague idea that the rank could be explained by the simple algorithm that generates these matrices. But now I'm not so sure. Let's look at the generation of magic(4). Start with the integers 1:16 arranged in a 4-by-4 array. This, of course, is a matrix with rank 1, but we're about to alter it drastically. Mark half of the elements with an asterisk in a pattern like this.
   1*    2     3     4*
   5     6*    7*    8
   9    10*   11*   12
  13*   14    15    16*
Now regard the marked elements as a one-dimensional array and flip that array end-for-end. This produces magic(4).
  16*    2     3    13*
   5    11*   10*    8
   9     7*    6*   12
   4*   14    15     1*
It must be easy to describe that indexing operation in matrix terms in a way that generalizes to higher order and explains why the resulting matrix happens to have rank 3. But I don't see how today.

Order Four

What about other 4-by-4 magic squares? Do they all have rank 3? Are there any nonsingular magic squares of order 4? I am able to answer that question because I came across this terrific paper by Bill Press, one of the authors of Numerical Recipes. Did Dürer Intentionally Show Only His Second-Best Magic Square? (I won't spoil Bill's punch line by revealing the answer to the question he poises in his title.) In order to investigate Dürer's possible choices for a special magic square, Press describes a seven variable parameterization of the 16 elements in a 4-by-4 array that characterizes all possible magic squares of order 4. (He attributes the parameterization to Maurice Kraitchik.) This approach leads to a program, enumerate.m, that checks the rank of all magic squares of order 4. This is the first time I have ever written a MATLAB code with for loops nested seven deep. It generates
16*15*14*13*12*11*10
= 57657600
matrices. Of these, only 7040 pass the check in the inner block to qualify as legal magic squares. Dividing the final counts by 8 to account for eight-fold symmetry, we find that that there are 880 magic squares of order four. Their ranks are
  rank  count
    3    640
    4    240
So, there ware nonsingular 4-by-4 magic squares. Other than that, I attach no great significant to the actual counts. The process of finding them is more interesting than the counts themselves. By the way, the entire computation by enumerate4 takes about 415 seconds on my Lenovo X201 2.67 GHz i7 laptop. The first nonsingular 4-by-4 magic square that enumerate4 finds is
   1     2    16    15
  13    14     4     3
  12     7     9     6
   8    11     5    10

Singly Even

The bar chart above shows that the rank for singly even magic squares, where n is divisible by two but not by four, is about $n/2$. Actually, the rank is $n/2+2$, and it is not hard to see why. The first step of the singly even algorithm is to stack together four copies of the square of odd order $n/2$.
  p = n/2;
  A = magic(p);
  M = [A A+2*p^2; A+3*p^2 A+p^2];
This M has equal column sums, but not equal row sums. And, since A has rank $n/2$, this M has rank $n/2+1$ The next step interchanges some blocks of elements to correct the row sums.
  i = (1:p)';
  k = (n-2)/4;
  j = [1:k (n-k+2):n];
  M([i; i+p],j) = M([i+p; i],j);
It turns out that this step does not change the rank. Now this M has equal row and column sums, but its diagonal sums are not quite right. The final step swaps two pairs of elements to correct the diagonal.
  i = k+1;
  j = [1 i];
  M([i; i+p],j) = M([i+p; i],j);
This is a rank one change that produces the final magic square and increases the rank to $n/2+2$.

Further Reading

William H. Press, Did Dürer Intentionally Show Only His Second-Best Magic Square?, 2009. CBM, Magic Squares chapter of Experiments with MATLAB, 2011.

Get the MATLAB code Published with MATLAB® R2012b

Note

Comments are closed.

4 CommentsOldest to Newest

Doug replied on : 1 of 4
That's a really interesting pattern! One minor point in the Doubly Even Order case - the rank of the initial 1:16 matrix is 2, not 1. Try: rank(reshape(1:16,4,4)) In fact, for any N>1, reshape(1:N^2,N,N) will have rank 2. So it seems that the rearranging operation to create the magic square always increases the rank by 1.
Jonathan replied on : 2 of 4
A quick search via Google reveals this link ("http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&cad=rja&ved=0CFUQFjAF&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.88.2717%26rep%3Drep1%26type%3Dpdf&ei=xMGjUJaJEeaVyAGN7YGQCg&usg=AFQjCNG8fLTdq8Hdxe3BC6VDfaNbXL0aAw&sig2=wtN5LgeLXduT7u_VqxWcRw") in which the following singular 5-by-5 matrix is shown. 2 11 21 23 8 16 14 7 6 22 25 17 13 9 1 4 20 19 12 10 18 3 5 15 24 This paper references another whose authors have found 656 singular magic squares of order 5.
Matthias replied on : 3 of 4
Thank your for your posts on magic squares. I really enjoy them. I found a 5x5 square with rank 4: A = [15 13 21 11 5; 10 2 23 16 14; 17 20 1 9 18; 4 24 12 22 3; 19 6 8 7 25]; ismagic = all([sum(A), sum(A'), sum(diag(A)), sum(diag(flipud(A)))] == (sum(1:length(A)^2)/length(A))) rank(A)
Cleve Moler replied on : 4 of 4
Francis Gaspalou sent me this email: My name is Francis Gaspalou, I am a French specialist of magic squares (I have a site about magic squares: http://www.gaspalou.fr/magic-squares/ ) In your blog – which is very interesting - , you write “Does anybody know of a 5-by-5 magic square that is also a singular matrix? I would love to see it”. I can answer your question. There are 646 singular magic squares of order 5 out of the total of 48,544 associative magic squares of order 5. You can see 2 examples of such singular magic squares on page 2676 of the paper of Peter Loly “magic square spectra” (dated 1 May 2009). You can find this paper on the web: you search with Google “magic square spectra” and the first reference you find is the author ‘s personal copy (LAA9954.pdf). This paper is a very good synthesis of the state of the art on the singular magic squares: - you are quoted in this paper on page 2668 - you will see also that the 640 singular magic squares of order 4 (out of the total of 880) are all very well known - there are a lot of data on singular magic squares, for example for the order 7 (ultramagic squares) - there is an excellent bibliography. For example I think you surely know the proof of Mattingly “Even order regular magic squares are singular” Am. Math. Monthly 107, November 2000, p. 777-782 -etc Peter Loly (loly@cc.umanitoba.ca) is truly the best reference for singular magic squares, eigenvalues and SVD analysis. Caution! This author calls “regular” magic square the squares which are usually called “associative” or “symmetrical”. Best regards Francis