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!
Best Answer
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$?