2
$\begingroup$

Consider all $n\times n$ binary (entries are either $0$ or $1$) matrices, denoted $\mathcal{B}_n$. Define the $X$-ray sequence of $A=(a_{ij})\in\mathcal{B}$ by $X(A)=x(1)x(2)\cdots x(2n-1)$ where $x(k)=\sum_{i+j=k+1}a_{ij}$. Then, the number of distinct $X$-ray sequences can be easily seen to be $n!(n+1)!$.

Example. Let $A=\begin{pmatrix} 1&2&3\\3&4&5\\0&1&2\end{pmatrix}$. Then $X(A)=15762$.

QUESTION. If we specialize to the subfamily $\mathcal{F}_n\subset\mathcal{B}_n$ of such invertible (over the field $\mathbb{F}_2$) matrices, then is there a formula for the total number $u_n$ of distinct $X$-ray sequences? If this is asking too much, how about an asymptotic growth of such enumeration?

NOTE. The cardinality of $\mathcal{F}_n$ is $\prod_{j=0}^{n-1}(2^n-2^j)$.

UPDATE. I've now computed a few terms: $u_1=1, u_2=5, u_3=77, u_4=2150$.

$\endgroup$
8
  • $\begingroup$ Have you computed these numbers for small $n$? $\endgroup$ Dec 31, 2020 at 17:19
  • $\begingroup$ If $n^2-n+1\geqslant \sum x_i\geqslant n$ (obviously necessary conditions), does not it follow that an invertible matrix exists? $\endgroup$ Dec 31, 2020 at 18:03
  • $\begingroup$ @RichardStanley: The Maple software I use needs updated licensing, so I have to wait for do computing. $\endgroup$ Dec 31, 2020 at 18:11
  • 2
    $\begingroup$ @FedorPetrov: an invertible matrix does not exist for $n=3$, $x(1)=1,x(2)=2,x(3)=0,x(4)=2,x(5)=1$. $\endgroup$ Dec 31, 2020 at 22:14
  • 1
    $\begingroup$ Is it true that if $A$ is a square matrix over a field $K$, then there is a diagonal matrix $D$ for which $A+D$ is nonsingular? (The answer is clearly yes if $K$ is infinite.) If so, then a lower bound for the number of X-ray sequences of invertible matrices over $\mathbb{F}_2$ is $n!^2$. $\endgroup$ Jan 1, 2021 at 0:02

1 Answer 1

5
$\begingroup$

I asked in a comment the following: Is it true that if $A$ is a square matrix over a field $K$, then there is a diagonal matrix $D$ for which $A+D$ is nonsingular? Here is a proof.

Induction on $n$. Clear for $n=1$. Assume for $n$. Let $B=(b_{ij})$ be an $(n+1)\times (n+1)$ matrix. Let $C$ be the submatrix indexed by $1\leq i\leq n$, $1\leq j\leq n$. By the induction hypothesis, there is a diagonal matrix $D=\mathrm{diag}(d_1,\dots,d_n)$ for which $C+D$ in nonsingular. Let $\alpha=\det(C+D)\neq 0$. Let $D'=\mathrm{diag}(d_1,\dots,d_n,0)$. Expand $\det(B+D')$. The coefficient of $b_{n+1,n+1}$ is $\alpha$. Since $\alpha\neq 0$, we can add $c=0$ or $c=1$ to $b_{n+1,n+1}$ to get a nonzero determinant. Hence $B+\mathrm{diag}(d_1,\dots,d_n,c)$ is nonsingular. $\ \ \Box$

Going back to the original problem, we can specify arbitrarily the entries off the main antidiagonal and then choose an antidiagonal making the determinant nonzero (by row and column permutations, it makes no difference here that we are looking at antidiagonals rather than diagonals), giving at least $n!^2$ X-ray sequences.

$\endgroup$
3
  • $\begingroup$ Moreover, we may choose such $D$ if $i$-th diagonal element is allowed to take only two distinct values. Proof: $\det(A+{\rm diag}(x_1,\ldots,x_n))$ is a multilinear polynomial in $x_1,\ldots,x_n$ with the coefficient of $x_1\ldots x_n$ equal to 1. Then the result follows from Combinatorial Nulltsellensatz. $\endgroup$ Jan 1, 2021 at 12:11
  • $\begingroup$ Ah, I see from your proof that you choose diagonal $D$ with 0's and 1's (and the proof is essentially the same), and use this refined statement. $\endgroup$ Jan 1, 2021 at 13:51
  • $\begingroup$ This is an interesting contribution. Upvoted. $\endgroup$ Jan 2, 2021 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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