3
$\begingroup$

A silver matrix of size $n$ is an $n\times n$ matrix where the ith row and ith column contain all the numbers in {1,2,\cdots, 2n-1}. For $n=2^k, k\ge 1$, find a formula for the number of silver matrices of size n.

I know that silver matrices of size $n > 1$ can only exist for n even. To show this, let the kth cross be the union of the entries in the kth row and kth column. There exists at least one element $x$ that is not on the main diagonal (because there are $n < 2n-1$ entries on the main diagonal). This entry must appear in $2$ distinct crosses, and in each of those crosses it appears once. Also $x$ appears in all crosses, so we may remove a row and column containing $x$ repeatedly to see that the number of crosses, or $n$, must be even (this is valid since no distinct occurrences of $x$ are in the same row or the same column, and thus each occurrence of $x$ corresponds to two unique crosses). Also note that by similar reasoning, no entry can appear an odd number of times on the main diagonal and if $y$ is an entry that appears $k$ times on the main diagonal, then it appears exactly $\frac{n-k}2$ times in off-diagonal entries. For $n=2,$ there are $3$ ways to choose the entry on the main diagonal, and for each of these ways there are $2$ ways to choose the positions of the remaining two entries. So there are $6$ silver matrices of size $2$. Let $S_n$ denote the number of silver matrices of size $n$ so that $S_2 = 6$.

To find the desired number of silver matrices, it might be useful to come up with a recurrence relation. For instance, one can split up a $2^k\times 2^k$ matrix into four $2^{k-1}\times 2^{k-1}$ submatrices, but these might not all be silver matrices. And the disjoint union of two silver matrices might not be a silver matrix.

$\endgroup$

1 Answer 1

1
$\begingroup$

This is far from a complete answer, but considering that no one has presented anything yet, I'm giving it in the hopes that someone else can build off it.

For any given $n$, let the set $S_n$ be the set of positive integers whose digits in base $n+1$ sum to $n$ and do not contain the digit $0$ in base $n+1$ (other than trivial leading zeroes). For example, $S_4=\{4_5,13_5,22_5,31_5,112_5,121_5,211_5,1111_5\}$. Let's define the function $f_n(x)$ taking an input $x$ from $S_n$ and returning the number of digits $x$ has in base $n+1$. Let's define the function $g_n(x,y)$, taking one input $x$ from $S_n$ and one $y$ from $\{1,2,3,...,f_n(x)\}$ and returning the $y$-th digit from the right of $x$ (in base $n+1$). For example, $g_4(211_5,1)=1,g_4(211_5,2)=1,g_4(211_5,3)=2$. Let's define the function $h_n(x,z)$, taking one input $x$ from $S_n$ and one $z$ from $\{2,3,...,f_n(x)\}$ returning the sum of the rightmost $z-1$ digits of $x$ in base $n+1$.

The number of distinct main diagonals of a silver $2n\times 2n$ matrix can be represented by (defining the empty product as equal to $1$) (note, that I have a mistake somewhere in the formula, as it doesn't quite align with what my derivation should yield; if someone can find it, that would help): $$M_{2n}=\sum_{x\in S_{n}}{}_{4n-1}P_{4n-1-f_n(x)}\sum_{y\in\{1,2,...,f_n(x)\}}\prod_{z\in\{2,3,...,y\}}{}_{2n-2h_n(x,z)}C_{2n-2h_n(x,z)-2g_n(x,y)+1}$$

To derive this, consider that $S_n$ are the ways we can assign the frequency of each element of the main diagonal (counting only those appearing at least once, and in order of first appearance), given that they need to appear an even number of times; for each of these, we have $m_1, m_2,...$ as the frequencies of this number that appears, in order of first appearance. For each of those, the ways we can assign them values are the permutation factor before the second summation. Then, after considering the frequency, we need to consider how to actually distribute those. The way we assigned the values to each of these, in order of the first time they appear, was given by the permutation factor. Then, we have $2n-1$ cells in which to assign the remaining $m_1-1$ elements that share a value with the first, then a remaining $2n-1-m_1$ cells in which to assign the remaining $m_2-1$ elements that share a value with the second distinct element to appear, and so on.

Additionally, as for any element off the main diagonal of a silver matrix $a_{i,j}$ is different from $a_{j,i}$ and there is no cross that contains only a single one of them, swapping their values creates a new distinct silver matrix. As there are $\frac{n^2-n}2$ such pairs of off-diagonal elements, we can establish a lower bound for the number of silver $n\times n$ matrices as $2^{\frac{n^2-n}2}M_n$.

Additionally, we can form an upper bound by noting that the first cross can be assigned in $(2n-1)!$ ways. Then, after assigning $k-1$ crosses, the $k$-th cross has $(2n-1-2(k-1))!=(2n+1-2k)!$ ways of assigning cells, giving an upper bound of: $$(2n-1)!\cdot(2n-3)!\cdot (2n-5)!\cdot ... \cdot (1)!$$.

Let's compare these bounds to the number of $2\times2$ and $4\times4$ silver matrices solved with brute force as (6 and 282240):

Our lower bounds give 4 and 1064 respectively. Our upper bounds give 6 and 3628800 respectively. The upper limit expands several orders of magnitude faster than the true value, and the lower limit expands several orders of magnitude slower, so both can probably be significantly improved

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .