# Prove the given matrix is invertible

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!

• Have a look at the matrix mod 2. Mar 18, 2022 at 12:20

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$$?

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)$$.

• Thanks for your answer. Unfortunately by the hypothesis every row and column is a permutation of $1,2,\ldots,2^{n-1}$, so the case you mentioned actually will not happen. But I think this idea is also fine, maybe could work with slight modification Mar 18, 2022 at 18:41