Given $n\geq 2$, let $M$ be a matrix with entries $1, \dots, n^2$, e.g.,
$$\begin{alignat*}{1} A_3 = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix} & \qquad A_4 = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12\\ 13 & 14 & 15 & 16 \end{pmatrix} \end{alignat*}$$
How do I prove that $\operatorname{rank}(M)=2$? I am supposed to use only the elementary row operations. For me, the definition of $\operatorname{rank}$ is number of non-zero rows in a row-echelon form.
For a specific $n$, I can actually perform the row operations and obtain the row-echelon form. However, I don't know how to prove it in general. Should I prove it using induction? How do I proceed with the induction step? The matrices $A_n$ and $A_{n+1}$ are completely different!
By the way, is there any specific name for this type of matrices?
Notice that the columns of $A_n$ obey this property: $$\vec v_n=2\vec v_{n-1} - \vec v_{n-2}$$
This means that only the first two columns are linearly independent, and everything after that can be represented as a linear combination of the the first two columns. Thus, $\rm Col(A)=2=Rank(A)$
Another solution using row reduction:
$R_2-R_1$ of every matrix is a row of $4$'s.
We can replace $R_2$ with $\frac{1}{4}(R_2-R_1)$ to get a row of $1's$. We can then replace every $R_n$ with $n \ge 3$ with $R_n-R_1-kR_2$ where $k$ is the number of $1$'s that need to be subtracted from $R_2-R_1$ to get a row of $0$'s.
Thus, we get the first row of $1,2,3 \ldots$ and the second row of just ones, rows that can't be turned into zeroes, meaning that $\rm Rank(A)=2$.
I do not know what these matrices are called.