4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Daishisan Jul 18 '14 at 3:59
  • 4
    $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Jul 18 '14 at 6:37
  • 2
    $\begingroup$ @Daishisan, because Noam's 5-dim affine space is actually 4-dimensional. And the rest indeed follows. $\endgroup$ – Włodzimierz Holsztyński Jul 18 '14 at 7:01
  • 2
    $\begingroup$ 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? $\endgroup$ – Stefan Kohl Jul 18 '14 at 10:19
  • 3
    $\begingroup$ 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 $\endgroup$ – Max Alekseyev Jul 18 '14 at 13:44
2
$\begingroup$

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.
This is such a wasteful construction that the question raised in my comment above might deserve some attention: what are good upper bounds for the common row and column sum of such a matrix?

$\endgroup$
  • 1
    $\begingroup$ 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}$$ $\endgroup$ – Robert Israel Jul 18 '14 at 17:51
  • $\begingroup$ ... 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}$$ $\endgroup$ – Robert Israel Jul 18 '14 at 19:47
  • 1
    $\begingroup$ @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. $\endgroup$ – Brendan McKay Jul 20 '14 at 8:07
  • 1
    $\begingroup$ 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)$$ $\endgroup$ – Brendan McKay Jul 20 '14 at 12:49
  • 1
    $\begingroup$ $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 }$$ $\endgroup$ – Robert Israel Jul 22 '14 at 21:14
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.