Independence of the columns of triangular matrices 
Let $M$ be a square upper triangular matrix with nonzero diagonal entries. Prove that the columns of $M$ are linear independent. 

I understand that this proof can be done with some sort of induction, but I don´t know how. Any help is appreciated.
(A square matrix $A=(a_{ij})$$i,j \in \{1,2, ...., n\}$ is said to be upper triangular if $a_{ij}=0$ for $i>j$.)
 A: Let $M_n$ denote a upper triangular square matrix of dimension $n$. We do induction on $n$. 
For the base case $n=1$, there is nothing to prove. 
Now, assume that the claim holds for $n-1, \ n>1.$ That is, if $v_1,v_2,...,v_{n-1}$ are the columns of $M_{n-1},$ then they are linearly independent. For the case $n$, let $v_n$ be the $n^{th}$ column of $M_n$. Since the diagonal entries are non-zero, it obviously cannot be a zero vector. 
Can you conclude now? 
A: Hint: prove that the $i$-th column cannot be obtained as a linear combination of the previous $i-1$ columns, by focusing on the $i-th$ entry of the vector. Then use induction (notice that for $n=1$ the statement is trivially true).
A: The induction argument is easy. The statement trivially holds for $n=1$. Now, for example, consider an $n\times n$ lower triangular matrix
$$
A=\begin{bmatrix}A_{11} & 0\\ * & \alpha_{22}\end{bmatrix}
$$
such that $A_{11}$ is $(n-1)\times (n-1)$ (lower triangular as well) and let the diagonal entries are nonzero. Assume that such a triangular matrix is nonsingular for the dimension one lower (that is, $A_{11}$ is nonsingular). Assume that $Ax=0$ and partition $x$ consistently with the partitioning of $A$. We have
$$
\begin{bmatrix}A_{11} & 0\\ * & \alpha_{22}\end{bmatrix}\begin{bmatrix}x_1\\\xi_2\end{bmatrix}=0.
$$
Hence $A_{11}x_1=0$ and thus $x_1=0$ by the induction assumption. Therefore, $\alpha_{22}\xi_2=0$ and since $\alpha_{22}\neq 0$, we have $\xi_2=0$. Consequently, $x=0$ and $A$ is nonsingular.
A: Lemma If $\{v_1,v_2,\dots,v_k\}$ is a linearly independent set and $v$ is not a linear combination of $v_1,v_2,\dots,v_k$, then the set $\{v_1,v_2,\dots,v_k,v\}$ is linearly independent.
Indeed, if
$$
\alpha_1v_1+\alpha_2v_2+\dots+\alpha_kv_k+\alpha v=0,
$$
we have two cases:


*

*$\alpha\ne0$

*$\alpha=0$
Case 1 cannot hold, as from the relation we can argue
$$
v=\beta_1v_1+\beta_2v_2+\dots+\beta_kv_k
$$
where $\beta_i=-\alpha^{-1}\alpha_i$ $(i=1,2,\dots,k)$: this contradicts $v$ not being a linear combination of $v_1,v_2,\dots,v_k$.
Therefore $\alpha=0$ and so $\alpha_1v_1+\alpha_2v_2+\dots+\alpha_kv_k=0$, so also
$\alpha_1=\alpha_2=\dots=\alpha_k=0$, by the linear independence hypothesis. QED
Now, let $v_i$ be the $i$-th column of $M$ $(i=1,2,\dots,n)$. The set $\{v_1\}$ is linearly independent and $v_2$ is not a linear combination of $v_1$, because row $2$ in $v_1$ is zero and row $2$ in $v_2$ is nonzero.
That was the base step of the induction. Assume we have proved that $\{v_1,\dots,v_k\}$ is linearly independent, with $1\le k<n$. Then $v_{k+1}$ is not a linear combination of $v_1,\dots,v_k$, because the $(k+1)$-th row in these vectors is zero and is nonzero in $v_{k+1}$. By the lemma above, $\{v_1,\dots,v_k,v_{k+1}\}$ is linearly independent.
