# $n\times n$ matrix with zero determinant?

Let $n\ge 3$ be a natural number, and for $1\leq k\leq n-2$ consider the $n\times n$ matrix

$$A_{n,k}=\begin{pmatrix} 1^{k}& 2^{k}& \cdots& n^{k}\\ (n+1)^k& (n+2)^k& \cdots& (2n)^k\\ \vdots& \vdots& & \vdots\\ (n^2-n+1)^k& (n^2-n+2)^k& \cdots& n^{2k} \end{pmatrix}_{\large{.}}$$

It seems that $\det (A_{n,k})=0$. I can prove this for $n=3$ and $k=1$, and for all $n\ge 4$ and $k=1,2.$ But my ways do not generalize to higher values of $k$.

Is there a simple proof that $\textbf{$\det(A_{n,k})=0$?}$

-
What is the exact Formula for $(A_{n,k})_{ij}$ ? –  AlexR Aug 22 '13 at 19:57

Notice that every row of the matrix is a linear combination of rows $(1^s,2^s,\dots,n^s)$, $0\leq s\leq k$ (just expand using binomial formula). So they must be linearly dependent.
Here's a different way to look at it and generalize it. Let's start with an easier problem: If instead we take a matrix of the first $n^2$ Fibonacci numbers (n>2) we also get a matrix with determinant 0. Why is this true? The third column will just be the sum of the first two.
Well if we replace the Fibonacci numbers by any sequence $A_i$ defined recursively where each term is a fixed linear combination of the previous m terms, then the same argument shows that a matrix filled with the first $n^2$ (with $n>m$) elements of this sequence will have determinant 0.
Now back to your problem, it would be enough to see that the sequence $1^k, 2^k, 3^k,...$ satisfies a fixed linear recurrence relation based on the previous k+1 terms. Well it just so happens that $a^k = {{k+1}\choose{1}}(a-1)^k - {{k+1}\choose{2}}(a-2)^k + {k+1\choose 3}(a-3)^k - ... \pm (a - k-1)^k$ for all $a$. (I didn't just pull that recurrence out of nowhere, there is a lot of great structure in the set of sequences satisfying some linear recurrence that one can exploit to find such relations)