# Induction proof of Leibniz determinant formula

I want to inductively proof that the denominator of the general solutions of an $$n \times n$$ system are given by the Leibnitz formula for the determinant \begin{align*} \sum_{\sigma \in S_{n}}^{} \text{sgn}\left(\sigma\right) \prod_{i = 1}^{n} a_{i, \sigma(i)} .\end{align*}

For the induction step, suppose our matrix $$\mathbf{A}\in \mathbb{R}^{n+1, n+1}$$ is given by $$( \mathbf{A})_{i, j} = a_{i, j}$$. My idea is now to eliminate the first column of the matrix (normal gaussian elimination) and consider the $$(n\times n)$$ submatrix $$(\mathbf{A})_{1:, 1:} = \widetilde{\mathbf{A}}$$ with \begin{align*} (\widetilde{\mathbf{A}})_{i, j} = \frac{a_{i+1, j+1}\cdot a_{1, 1}- a_{1, j+1}\cdot a_{i+1, 1}}{a_{1, 1}} .\end{align*} To this matrix we can apply the formula we assume to be true, so what I want to show is \begin{align*} a_{1, 1}\sum_{\sigma \in S_{n}}^{} \text{sgn}\left(\sigma\right) \prod_{i = 1}^{n} (\widetilde{\mathbf{A}})_{i, \sigma(i)} = \sum_{\sigma \in S_{n+1}}^{} \text{sgn}\left(\sigma\right) \prod_{i = 1}^{n+1} a_{i, \sigma(i)} .\end{align*} (The additional factor $$a_{1, 1}$$ comes from the fact that for getting the denominator of the general solution we have to bring it to the other site and there it will cancel out, but this we don't consider when applying the formula directly to the submatrix). However, I didn't come very far in my proof \begin{align*} a_{1, 1}\sum_{\sigma \in S_{n}}^{} \text{sgn}\left(\sigma\right) \prod_{i = 1}^{n} (\widetilde{\mathbf{A}})_{i, \sigma(i)} &= a_{1, 1}\sum_{\sigma \in P_{n+1}}^{} \text{sgn}\left(\sigma\right) \prod_{i = 1}^{n} \left( \frac{a_{i+1, \sigma(i+1)}\cdot a_{1, 1}- a_{1, \sigma(i+1)}\cdot a_{i+1, 1}}{a_{1, 1}} \right) \\[5pt] &= a_{1, 1}\sum_{\sigma \in P_{n+1}}^{} \text{sgn}\left(\sigma\right) \prod_{i = 2}^{n+1} \left( \frac{a_{i, \sigma(i)}\cdot a_{1, 1}- a_{1, \sigma(i)}\cdot a_{i, 1}}{a_{1, 1}} \right) \\[5pt] &= \sum_{\sigma \in P_{n+1}}^{} \frac{\text{sgn}\left(\sigma\right)}{(a_{1, 1})^{n-1}} \prod_{i = 2}^{n+1} \left( {a_{i, \sigma(i)}\cdot a_{1, 1}- a_{1, \sigma(i)}\cdot a_{i, 1}} \right) \end{align*} Could someone help me with the proof?

Edit: $$P_{n+1}$$ denotes the permutations of the elements $$\{2, 3, \ldots, n+1\}$$. Also, in the comments the Neville algorithm got mentioned, but I don't see the connection yet.

• Commented Jan 2, 2022 at 16:14
• @ErikSatie could you maybe elaborate? I don't immediately see the connection.
– Rhi
Commented Jan 2, 2022 at 16:20
• Are you trying to prove Cramer's rule (en.wikipedia.org/wiki/Cramer%27s_rule#General_case)? Commented Jan 2, 2022 at 22:56
• @Mason not really, I'm trying to proof Leibniz's rule (but not from the constructive point of view where you derive it using the properties)
– Rhi
Commented Jan 3, 2022 at 10:19
• @Rhi What exactly are you trying to prove? The thing about the determinant being in the denominator of the solutions sounds like Cramer's rule. Commented Jan 4, 2022 at 20:28