Why every $(n-2)\times(n-2)$-submatrix of this $(n-2)\times n$ matrix has full rank?

Let $$A$$ be an $$(n-2)\times n$$ matrix such that for every $$i=1,2,...,n-2$$ the $$i$$th row consists of $$1, -2, 1$$ at $$i$$th, $$(i+1)$$st, and $$(i+2)$$nd column, respectively, and all other entries are $$0$$.

Then $$n$$-term arithmetic progressions are some integer solutions of $$Ax=0$$.

It is said that every $$(n-2)\times(n-2)$$ submatrix of $$A$$ has full rank. I am wondering why?

I have a feeling that after crossing out two columns except the first or the last one, the remaining square matrix is upper triangular with non-zero diagonal entries. But is there a way to prove it?

2 Answers

Presumably the matrix is real. After removing two columns from $$A$$, what remains is $$B=\begin{bmatrix}U&X&0\\ 0&S&0\\ 0&Y&L\end{bmatrix} =\left[\begin{array}{cccc|cccc|cccc} 1&-2\\ &\ddots&\ddots\\ &&\ddots&-2\\ &&&1&1\\ \hline &&&&-2&1\\ &&&&1&\ddots&\ddots\\ &&&&&\ddots&\ddots&1\\ &&&&&&1&-2\\ \hline &&&&&&&1&1\\ &&&&&&&&-2&\ddots\\ &&&&&&&&&\ddots&\ddots\\ &&&&&&&&&&-2&1\\ \end{array}\right].$$ Therefore $$\det(B) =\det\left[\begin{array}{c|cc}U&X&0\\ \hline 0&S&0\\ 0&Y&L\end{array}\right] =\det(U)\det\begin{bmatrix}S&0\\ Y&L\end{bmatrix} =\det(U)\det(S)\det(L).$$ Clearly, the upper triangular sub-block $$U$$ and the lower triangular sub-block $$L$$ are nonsingular. The symmetric sub-block $$S$$ is also nonsingular because $$-S =\begin{bmatrix}1&-1\\ &\ddots&\ddots\\ &&\ddots&-1\\ &&&1\end{bmatrix} \begin{bmatrix}1\\ -1&\ddots\\ &\ddots&\ddots\\ &&-1&1\end{bmatrix} +\begin{bmatrix}0\\ &\ddots\\ &&0\\ &&&1\end{bmatrix}$$ is positive definite. It follows that $$B$$ is nonsingular.

• Why $-S$ is positive definite? In the sum, I can see the last is non-negative definite, but why the product of two symmetric matrices is positive definite? Oct 31, 2019 at 18:28
• @Connor The sum of a positive definite and a positive semidefinite matrix is positive definite. Oct 31, 2019 at 18:41

Here is a different style of proof.

First, note that by its very construction, if $$Av = 0$$ then $$v$$ is an $$n$$-term arithmetic sequence. (What is an arithmetic sequence anyway? It is one where every term is the average (arithmetic mean) of the previous and next terms.)

Now assume for future contradiction that some $$(n-2)$$ columns are linearly dependent. Consider $$B_{(n-2) \times (n-2)}$$ which is $$A$$ restricted to these columns. $$B$$ does not have full rank, so there exists $$x \neq 0$$ s.t. $$Bx = 0$$. Now extend $$x$$ back into a $$n$$-term vector $$y$$ by filling in the two missing places with $$0$$. So we have $$Ay=0$$ where:

• $$y \neq 0$$

• but $$y$$ has at least two entries which are $$0$$

But such a $$y$$ cannot be an arithmetic sequence, because no arithmetic sequence can have two entries being $$0$$ unless it is all $$0$$s. Thus we have the contradiction we need.

• Very nice. +1$\phantom{}$ Nov 4, 2019 at 20:35