Le Monde puzzle [#755?]

Le Monde puzzle of last weekend was about sudoku-like matrices.

Consider an (n,n) matrix containing the integers from 1 to n². The matrix is “friendly” if the set of the sums of the rows is equal to the set of the sum of the columns. Find examples for n=4,5,6. Why is there no friendly matrix when n=9?

Checking for small n’s seems easy enough:

friend=function(n){
s=1
while (s>0){
  A=matrix(sample(1:n^2),ncol=n)
  s=sum(abs(sort(apply(A,1,sum))-
        sort(apply(A,2,sum))))}
A
}

For instance, running

> friend(3)
     [,1] [,2] [,3]
[1,]    8    4    2
[2,]    1    9    5
[3,]    6    3    7
> friend(4)
     [,1] [,2] [,3] [,4]
[1,]   14   10   11    6
[2,]   13    3   12    8
[3,]    4    5   16   15
[4,]    9    1    2    7
> friend(5)
     [,1] [,2] [,3] [,4] [,5]
[1,]   17   14   10   16    5
[2,]    8   19    7   15   22
[3,]    2    3   25   13    6
[4,]   11   12   18    1   21
[5,]   24   23   20    4    9
>friend(6)
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]   14    4   36   30   10   18
[2,]    7   16   24   27   32   11
[3,]   21   25   12    5   22   17
[4,]   26   20    6   31   19   34
[5,]    3   35    1   28    9   29
[6,]   23    2   33   15   13    8

produces right answers. But the case n=6 proved itself almost too hard for brute-force handling!!! I have no time to devise a simulated-annealing code to speed up the resolution so this will have to wait till the next weekend edition of Le Monde. As to why n=9 does not enjoy a solution… (When n=2 there is no solution, as proven by the brute force exhibition of all cases.)