# Magic squares with specific properties

For what $n \geq 3$ does there exist an $n \times n$ matrix such that:

• All entries are in $(0, 1)$.
• Each row and column sums to $1$.
• Aside from the rows and columns, no other subsets of the entries sum to $1$.

EDIT: I had a comment about $n = 3$ likely not being possible, but I removed that now after some helpful comments.

• Theoretically they're fine, but if there is a $0$, then in that row we could just take $n - 1$ nonzero entries and they would sum to $1$ --- thus breaking the third condition. So there's no point in allowing them. – Daishisan Jul 18 '14 at 3:59
• For $n=3$ there's a 5-dimensional (affine) space of solutions, and it seems that generically there's no other subset that sums to $1$, so as long as you avoid a finite number of hyperplanes you're fine. – Noam D. Elkies Jul 18 '14 at 6:37
• @Daishisan, because Noam's 5-dim affine space is actually 4-dimensional. And the rest indeed follows. – Włodzimierz Holsztyński Jul 18 '14 at 7:01
• Why do you require $n \geq 3$? -- For $n = 1$ the problem becomes trivial (take the matrix with the only entry equal to $1$), and for $n = 2$ you can take e.g. the matrix $$\left(\begin{array} \ 1/3 & 2/3 \\ 2/3 & 1/3 \\ \end{array}\right)$$ -- or did I get something wrong? – Stefan Kohl Jul 18 '14 at 10:19
• Why you call it magic square (which is typically composed of integers)? It looks more like a doubly stochastic matrix en.wikipedia.org/wiki/Doubly_stochastic_matrix – Max Alekseyev Jul 18 '14 at 13:44

Such a matrix (integer version) can be constructed from a magic square, say with entries $1,\dots,n^2$, by adding suitable multiples of all $n\times n$ permutation matrices: e.g. take $N=n^2$ and add all $N^iP_i$, where $P_1, \dots,P_{n!}$ are in any order.
• Here's a $4 \times 4$ example for $k = 3302$ (not claimed to be optimal): $$\pmatrix{2921 & 334 & 41 & 6\cr 191 & 1885 & 433 & 793\cr 125 & 382 & 1413 & 1382\cr 65 & 701 & 1415 & 1121\cr}$$ – Robert Israel Jul 18 '14 at 17:51
• ... and now one with $k=1511$: $$\pmatrix{268 & 207 & 977 & 59\cr 535 & 379 & 118 & 479\cr 73 & 153 & 332 & 953 \cr 635 & 772 & 84 & 20\cr}$$ – Robert Israel Jul 18 '14 at 19:47
• @Robert: $k=480$ $$\left(\begin{matrix} 102& 132& 148& 98\\ 118& 78& 147& 137\\ 139& 170& 66 &105\\ 121 &100& 119& 140\end{matrix}\right)$$ Found by random hill-climbing. – Brendan McKay Jul 20 '14 at 8:07
• And $k=460$: $$\left(\begin{matrix} 82& 109& 103& 166\\ 94& 135& 125& 106\\ 102& 121& 133& 104\\ 182& 95& 99& 84 \end{matrix}\right)$$ – Brendan McKay Jul 20 '14 at 12:49
• $k=430$ (must be getting close to optimality...): $$\pmatrix{ 62 & 152 & 104 & 112 \cr 153 & 90 & 94 & 93 \cr 102 & 89 & 132 & 107 \cr 113 & 99 & 100 & 118 \cr }$$ – Robert Israel Jul 22 '14 at 21:14
Consider the general integer version of the problem: given positive integers $n$ and $K$, find an $n \times n$ matrix of positive integers whose row and column sums are $K$, and no set of matrix elements that is not a row or column sums to $K$. In principle, you can find a $K$ for which this is is possible as follows.
Consider producing your matrix $M$ as the sum of $K$ random permutation matrices, each of which is chosen independently and uniformly from the $n!$ possible permutations. If $S$ is any subset of the entries that is not a row or column, let $Y_S = \sum_{(i,j) \in S} M_{ij}$ be the sum of this subset of the entries of $M$. Now the cardinality of the intersection of $S$ with a random permutation matrix is a random variable that is not a.s. $1$. We can then estimate the probability that $Y_S$, which is the sum of $K$ iid random variables with this distribution, is equal to $K$: in general it should decay like $1/\sqrt{K}$ if $|S| = n$ (which makes the mean of the random variable $1$), and more rapidly if $|S| \ne n$. As soon as $K$ is large enough that the expected number of subsets $S$ with $Y_S = K$ is less than $1$, we know that with positive probability all $Y_S \ne K$, and thus a solution with this $K$ is possible.