Prove the given matrix is invertible

Question

Question. Let $A$ be an $n\times n$ matrix such that each row and each column of $A$ contains all of the entries $1,2,2^2,...,2^{n-1}$ in some order. Prove that $A$ is invertible.

An easy fact is that $(2^n-1,e)$ is an eigenpair of $A$ where $e\in\mathbb{R}^n$ is a vector of all-one entries. However, this is not sufficient for proving $A$ is invertible.

One possible route is to prove $0$ is not an eigenvalue of $A$. I am also thinking about Gershgorin discs. The deleted absolute row sum on the $k$-th row is $2^n-1-a_{kk}$. Thus the Gershgorin disc is $$D_k:=\{z\in\mathbb{C}\mid|z-a_{kk}|\le2^n-1-a_{kk}\}.$$ If $0\notin D_k$, then $$a_{kk}=|0-a_{kk}|>2^n-1-a_{kk}\implies a_{kk}>2^{n-1}-\frac12.$$ In other words, only if $a_{kk}=2^{n-1}$ will $0\notin D_k$ happen. For the structure of $A$, I am thinking about a sudoku-like array, so it is not guaranteed that the diagonal entries of $A$ are all $2^{n-1}$. For instance, $$\begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix},\quad\begin{bmatrix} 1 & 2 & 4 \\ 4 & 1 & 2 \\ 2 & 4 & 1 \end{bmatrix},\quad\begin{bmatrix} 1 & 2 & 4 & 8 \\ 2 & 4 & 8 & 1 \\ 4 & 8 & 1 & 2 \\ 8 &1 &2 & 4 \end{bmatrix}.$$ In particular, permutation similarity does not change the diagonal entries. Currently I am stuck at this point. Any clever ideas or suggestions are highly welcomed.

---

Update. Thanks for all the comments and solutions suggested below! Jimmy’s hint is almost detailed and close to the arguments for proving the Gershgorin disc theorem. I am also conjecturing if there is no dominating terms among a given sequence (here $2^{n-1}$ is dominating as the sum of all other terms is $2^{n-1}-1$), then such matrix $A$ might be singular.

Micheal’s smart comment exploits the special structure here. Let me write down the details for future readers. By taking all the entries modulo 2, we get a permutation matrix, whose determinant is $\pm 1$. Thus the determinant of $A$ is odd and cannot be zero.

---

Update 2. My conjecture is true. The following matrix is singular: $$\begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \end{bmatrix}.$$ I am beyond happy that I could communicate with your guys about this question!

Answer 1

Hint: Suppose $A$ is not invertible, and thus, there exists a vector $v \neq 0$ such that $Av = 0$.

Let $i$ be an index which satisfies $|v_i| \ge |v_j|$ for $j = 1,\ldots,n$, and then let $r$ be the row such that $A_{r,i} = 2^{n-1}$. Is it possible for $\displaystyle\sum_{j = 1}^{n}A_{r,j}v_j = (Av)_r = 0$?

Answer 2

Here is another way to prove that $A$ is invertible. We will use the author's remark about the eigenvector.

Suppose $\operatorname{det}(A)=0$.

1. Then it is easy to think that either in some column or in some row of matrix $A$ occurs at least twice $1$ (why?). Let's say $1$ occurs twice in some column.

2. Then there exists a column with no $1$. So all the elements of that column are even.

3. The latter contradicts the equality $eA=(2^n-1)e$, where $e=(1,\ldots,1)$.