Let's say we have a polynomial $p(z)=\sum_{i=0}^n c_iz^i$. If we have $n+1$ known values $(z_i,w_i)$. We find \begin{align*} \sum_{i=0}^n c_iz_0^i&=w_0\\ &\vdots\\ \sum_{i=0}^n c_iz_n^i&=w_n \end{align*}
Which comes down to row-reducing \begin{equation} \left( \begin{array}{cccc|c} 1c_1&z_0c_2&\ldots&z_0^n c_{n+1}&w_0\\ 1c_1&z_1c_2&\ldots&z_1^nc_{n+1}&w_1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 1c_1&z_nc_2&\ldots&z^n_nc_{n+1}&w_n \end{array} \right)\label{matrix} \end{equation} For $i\neq j$ it holds that $z_i\neq z_j$. why do the rows have to be linearly independent, aka there has to be a unique solution for all the $c_i$. Therefore $p$ being determined by $n+1$ values?
Without using the fundamental theorem of algebra!