Felix' Math Place (Posts about Cramer's rule.)https://math.fontein.de/tag/cramers-rule.atom2019-11-17T10:38:16ZFelix FonteinNikolaOn a Certain Determinant.https://math.fontein.de/2011/03/25/on-a-certain-determinant/2011-03-25T09:55:14+01:002011-03-25T09:55:14+01:00Felix Fontein<div>
<p>
Yesterday, I managed to compute a determinant of a certain matrix. This matrix appears in the work I'm currently doing, and having an explicit formula for it allowed me to explicitly solve a system of linear equations using <a href="https://en.wikipedia.org/wiki/Cramer%2527s_rule">Cramer's rule</a>. In this post, I want to present the result with two different proofs by induction.
</p>
<p>
I wouldn't be surprised if this is already well-known, but at least I didn't see it before. Anyway, if you have seen it before, please feel free to tell me about it.
</p>
<p>
<strong>Edit:</strong> in fact, the theorem follows from the more general result stated <a href="http://planetmath.org/encyclopedia/DeterminantsOfSomeMatricesOfSpecialForm.html">here</a>. Also see the <a href="https://math.fontein.de/2011/03/25/on-a-certain-determinant/#comment-286">comments</a>.
</p>
<div class="theorem-environment theorem-theorem-environment">
<div class="theorem-header theorem-theorem-header">
Theorem.
</div>
<div class="theorem-content theorem-theorem-content">
<p>
Let <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="12" src="https://math.fontein.de/formulae/08bW5Zvy2ST6Ewwt6yOyAbfn7ZY0nrbV5GNE.Q.svgz" alt="K" title="K"></span> be a field and <span class="inline-formula"><img class="img-inline-formula img-formula" width="115" height="16" src="https://math.fontein.de/formulae/mSpIF464jX7vtpKjZM8OwXjWX3VNUQlzK43hjg.svgz" alt="x_1, \dots, x_n \in K" title="x_1, \dots, x_n \in K"></span>. Then the matrix
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="436" height="109" src="https://math.fontein.de/formulae/NaN7N9LszXcNtncGX7LN8zAgOrgtMNswBX.JWQ.svgz" alt="M(x_1, \dots, x_n) :=
\Matrix{ 1 + x_1 & 1 & \cdots & 1 \\ 1 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & 1 \\
1 & \cdots & 1 & 1 + x_n } \in K^{n \times n}" title="M(x_1, \dots, x_n) :=
\Matrix{ 1 + x_1 & 1 & \cdots & 1 \\ 1 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & 1 \\
1 & \cdots & 1 & 1 + x_n } \in K^{n \times n}">
</div>
<p>
has determinant
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="142" height="55" src="https://math.fontein.de/formulae/1miy4BDgoglZFrRY1TDQ2Iz_gEqWyjuMDNgP_Q.svgz" alt="\prod_{i=1}^n x_i + \sum_{j=1}^n \prod_{i \neq j} x_i." title="\prod_{i=1}^n x_i + \sum_{j=1}^n \prod_{i \neq j} x_i.">
</div>
</div>
</div>
<p>
Before I present the proofs, I want to say a few words on how this matrix comes up. Consider the linear system <span class="inline-formula"><img class="img-inline-formula img-formula" width="55" height="12" src="https://math.fontein.de/formulae/w3I5pvecVqA7qrPENDNxGbfRg3q8cXPFIKGvsw.svgz" alt="A x = b" title="A x = b"></span>, where
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="457" height="97" src="https://math.fontein.de/formulae/xkGQp6mrhlyK532iM4CIYc3kXvkUligxsjL19A.svgz" alt="A = \Matrix{ y_1 & & 0 \\ & \ddots & \\ 0 & & y_n \\ 1 & \cdots & 1 } \in \R^{(n + 1) \times n} \quad \text{and} \quad
b = \Matrix{ 0 \\ \vdots \\ 0 \\ 1 } \in \R^{n+1}." title="A = \Matrix{ y_1 & & 0 \\ & \ddots & \\ 0 & & y_n \\ 1 & \cdots & 1 } \in \R^{(n + 1) \times n} \quad \text{and} \quad
b = \Matrix{ 0 \\ \vdots \\ 0 \\ 1 } \in \R^{n+1}.">
</div>
<p>
Assuming that all <span class="inline-formula"><img class="img-inline-formula img-formula" width="47" height="16" src="https://math.fontein.de/formulae/Dh3YaCInCx2i2pyZh.6HbFzOWgxZ_u.HaE1wZw.svgz" alt="y_i \neq 0" title="y_i \neq 0"></span>, one sees that this system has <em>no</em> solution. Instead, one can try to find a vector <span class="inline-formula"><img class="img-inline-formula img-formula" width="10" height="8" src="https://math.fontein.de/formulae/VCj4le645BgRKl_EPkn4ejR4nVs2ZZW2.MXY9Q.svgz" alt="x" title="x"></span> which minimizes <span class="inline-formula"><img class="img-inline-formula img-formula" width="78" height="18" src="https://math.fontein.de/formulae/pZ0gJ4Zb4.HVEfSfBS0VaKHTQrwxd5nCpj26Yw.svgz" alt="\| A x - b \|_2" title="\| A x - b \|_2"></span>. A well-known fact in Linear Algebra says that this is the case for a unique <span class="inline-formula"><img class="img-inline-formula img-formula" width="10" height="8" src="https://math.fontein.de/formulae/VCj4le645BgRKl_EPkn4ejR4nVs2ZZW2.MXY9Q.svgz" alt="x" title="x"></span>, and that <span class="inline-formula"><img class="img-inline-formula img-formula" width="10" height="8" src="https://math.fontein.de/formulae/VCj4le645BgRKl_EPkn4ejR4nVs2ZZW2.MXY9Q.svgz" alt="x" title="x"></span> is the solution to the system <span class="inline-formula"><img class="img-inline-formula img-formula" width="104" height="15" src="https://math.fontein.de/formulae/DpUQoJ8MbqNMfiXSo2NHi97DyYVNHatQYgFe1Q.svgz" alt="A^T A x = A^T b" title="A^T A x = A^T b"></span>. Now <span class="inline-formula"><img class="img-inline-formula img-formula" width="169" height="19" src="https://math.fontein.de/formulae/NXUdr47jwrISNCuP1r9S46w5wZ3vde4_vpgfyw.svgz" alt="A^T A = M(y_1^2, \dots, y_n^2)" title="A^T A = M(y_1^2, \dots, y_n^2)"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="138" height="19" src="https://math.fontein.de/formulae/g6b.ZWKzvH13dOEZAjL01oEkL0gG5.lW7IiaAA.svgz" alt="A^T b = (1, \dots, 1)^T" title="A^T b = (1, \dots, 1)^T"></span>, whence we can describe the unique solution <span class="inline-formula"><img class="img-inline-formula img-formula" width="136" height="19" src="https://math.fontein.de/formulae/Lox0nxDaiKF0V4O_0528qqt1bZ8D4Zf.HjHOkg.svgz" alt="x = (x_1, \dots, x_n)^T" title="x = (x_1, \dots, x_n)^T"></span> using Cramer's rule by
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="313" height="44" src="https://math.fontein.de/formulae/Fr6ghIaYlFZMfF2sLKqioixE0DIempaQnktL9g.svgz" alt="x_i = \frac{\det M(y_1^2, \dots, y_{i-1}^2, 0, y_{i+1}^2, \dots, y_n^2)}{\det M(y_1^2, \dots, y_n^2)}." title="x_i = \frac{\det M(y_1^2, \dots, y_{i-1}^2, 0, y_{i+1}^2, \dots, y_n^2)}{\det M(y_1^2, \dots, y_n^2)}.">
</div>
<p>
Now the above theorem gives an easy to evaluate formula for the determinants, namely
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="244" height="49" src="https://math.fontein.de/formulae/JLLVQaOBA17Ayxp3PQ7ghCLOSpoGNxUK6T03cA.svgz" alt="x_i = \frac{\prod_{j \neq i} y_j^2}{\prod_{j=1}^n y_j^2 + \sum_{k=1}^n \prod_{j \neq k} y_j^2}." title="x_i = \frac{\prod_{j \neq i} y_j^2}{\prod_{j=1}^n y_j^2 + \sum_{k=1}^n \prod_{j \neq k} y_j^2}.">
</div>
<p>
The solution vector <span class="inline-formula"><img class="img-inline-formula img-formula" width="10" height="8" src="https://math.fontein.de/formulae/VCj4le645BgRKl_EPkn4ejR4nVs2ZZW2.MXY9Q.svgz" alt="x" title="x"></span> can be evaluated in <span class="inline-formula"><img class="img-inline-formula img-formula" width="38" height="18" src="https://math.fontein.de/formulae/uIosFPidJLezb7r7bpfRHiawaBBfUd6kFYLEmw.svgz" alt="O(n)" title="O(n)"></span> operations, and in case the <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="11" src="https://math.fontein.de/formulae/0X6GQGIgJjCQdZ17cY.Uf9op.5NTFjjahnmPXA.svgz" alt="y_i" title="y_i"></span> are rational numbers, one can hence efficiently compute an exact (i.e. rational) solution.
</p>
<div class="theorem-environment theorem-proof-environment qed">
<div class="theorem-header theorem-proof-header">
Proof (First proof).
</div>
<div class="theorem-content theorem-proof-content">
<p>
For <span class="inline-formula"><img class="img-inline-formula img-formula" width="60" height="15" src="https://math.fontein.de/formulae/vIBXwMxGnWS2x4rOvCXcnqaQ2eXDvcfVu.dPsA.svgz" alt="n = 1, 2" title="n = 1, 2"></span> this is easy to verify. Hence, assume that <span class="inline-formula"><img class="img-inline-formula img-formula" width="43" height="14" src="https://math.fontein.de/formulae/cB7lFDFLsqLOwcRM5dujHZDisfPIpjFynNPIeA.svgz" alt="n \ge 3" title="n \ge 3"></span> and that the statement is true for <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="13" src="https://math.fontein.de/formulae/VNmylc5SS6m0GoMzxOh2C.o19W3wV1wyQtDHlQ.svgz" alt="n - 1" title="n - 1"></span>. Using the multilinearity of the determinant and Lagrange expansion, both for the first row, we see that
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="504" height="18" src="https://math.fontein.de/formulae/hVCUiW00WC3Alm2m6OjfmhM89Sry4t8O8bJU9A.svgz" alt="\det M(x_1, \dots, x_n) = x_1 \det M(x_2, \dots, x_n) + \det M(0, x_2, \dots, x_n)." title="\det M(x_1, \dots, x_n) = x_1 \det M(x_2, \dots, x_n) + \det M(0, x_2, \dots, x_n).">
</div>
<p>
The same argument applied to the second row of the second determinant, we obtain that the second determinant
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="373" height="18" src="https://math.fontein.de/formulae/SF2EjQGYfBWK0ZbLZzk6iQZz3.WtBV8Tlbid7w.svgz" alt="x_2 \det M(0, x_3, \dots, x_n) + \det M(0, 0, x_3, \dots, x_n)." title="x_2 \det M(0, x_3, \dots, x_n) + \det M(0, 0, x_3, \dots, x_n).">
</div>
<p>
Since <span class="inline-formula"><img class="img-inline-formula img-formula" width="144" height="18" src="https://math.fontein.de/formulae/q22XSiZOIS08f1wpeBV8PhyKksOVwbU.zZqqAw.svgz" alt="M(0, 0, x_3, \dots, x_n)" title="M(0, 0, x_3, \dots, x_n)"></span> has two identical rows – namely the first two –, its determinant is 0. Moreover, by induction hypothesis, <span class="inline-formula"><img class="img-inline-formula img-formula" width="237" height="20" src="https://math.fontein.de/formulae/2AkrKRFv84vH1YtPzrH2l4Jk85TU9gHiUoBGIQ.svgz" alt="\det M(0, x_3, \dots, x_n) = \prod_{i=3}^n x_i" title="\det M(0, x_3, \dots, x_n) = \prod_{i=3}^n x_i"></span> and
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="304" height="61" src="https://math.fontein.de/formulae/nE2Bt_HjFug5HqAxoYYvAs7O6oBIMby0rNxtVQ.svgz" alt="\det M(x_2, \dots, x_n) = \prod_{i=2}^n x_i + \sum_{j=2}^n \prod_{i=2 \atop i \neq j}^n x_i." title="\det M(x_2, \dots, x_n) = \prod_{i=2}^n x_i + \sum_{j=2}^n \prod_{i=2 \atop i \neq j}^n x_i.">
</div>
<p>
Plugging this in yields
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="410" height="61" src="https://math.fontein.de/formulae/jOm7S4S9o7UY6h.6L4.FU.5o5ZD_8HlfdUNZIA.svgz" alt="\det M(x_1, \dots, x_n) = x_1 \prod_{i=2}^n x_i + x_1 \sum_{j=2}^n \prod_{i=2 \atop i \neq j}^n x_i + \prod_{i=2}^n x_i," title="\det M(x_1, \dots, x_n) = x_1 \prod_{i=2}^n x_i + x_1 \sum_{j=2}^n \prod_{i=2 \atop i \neq j}^n x_i + \prod_{i=2}^n x_i,">
</div>
<p>
which shows the claim.
</p>
</div>
<div class="qed-block"><span class="qed-sign"></span></div>
</div>
<div class="theorem-environment theorem-proof-environment qed">
<div class="theorem-header theorem-proof-header">
Proof (Second proof).
</div>
<div class="theorem-content theorem-proof-content">
<p>
For <span class="inline-formula"><img class="img-inline-formula img-formula" width="43" height="11" src="https://math.fontein.de/formulae/AI3jLOaiR4OxpS_JgU78KWnQ5jO4jP6BS3hJew.svgz" alt="n = 1" title="n = 1"></span> this is clear. Hence, assume that <span class="inline-formula"><img class="img-inline-formula img-formula" width="43" height="12" src="https://math.fontein.de/formulae/reArLJOpe3J6eHLpP4vd0OMCtQxU46viESPUfA.svgz" alt="n > 1" title="n > 1"></span> and that the statement is true for <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="13" src="https://math.fontein.de/formulae/VNmylc5SS6m0GoMzxOh2C.o19W3wV1wyQtDHlQ.svgz" alt="n - 1" title="n - 1"></span>. We do a Lagrange expansion by the last column. This yields a term <span class="inline-formula"><img class="img-inline-formula img-formula" width="288" height="19" src="https://math.fontein.de/formulae/eHrBzOuxb.lm.7RJPMUJ1dsWZlsmJlv.x44ytA.svgz" alt="(-1)^{n + n} (1 + x_n) \det M(x_1, \dots, x_{n-1})" title="(-1)^{n + n} (1 + x_n) \det M(x_1, \dots, x_{n-1})"></span>, which by induction hypothesis equals
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="309" height="64" src="https://math.fontein.de/formulae/PLeqRAtO4shXlrPVlMI4neDEZr57t.n2O_acMg.svgz" alt="\prod_{i=1}^{n-1} x_i + \sum_{j=1}^{n-1} \prod_{i=1 \atop i \neq j}^{n-1} x_i + \prod_{i=1}^n x_i + \sum_{j=1}^{n-1} \prod_{i=1 \atop i \neq j}^n x_i." title="\prod_{i=1}^{n-1} x_i + \sum_{j=1}^{n-1} \prod_{i=1 \atop i \neq j}^{n-1} x_i + \prod_{i=1}^n x_i + \sum_{j=1}^{n-1} \prod_{i=1 \atop i \neq j}^n x_i.">
</div>
<p>
The other terms are of the form <span class="inline-formula"><img class="img-inline-formula img-formula" width="116" height="19" src="https://math.fontein.de/formulae/pXqXV0xoAa.raTpVgIxwb5UohYlbfHyMqXz0IA.svgz" alt="(-1)^{n + i} \det M_i" title="(-1)^{n + i} \det M_i"></span>, where <span class="inline-formula"><img class="img-inline-formula img-formula" width="23" height="15" src="https://math.fontein.de/formulae/N23AF6eNmrAlqUmjiacGN5u_43aLeJC6JFMcuQ.svgz" alt="M_i" title="M_i"></span> is <span class="inline-formula"><img class="img-inline-formula img-formula" width="110" height="18" src="https://math.fontein.de/formulae/ZykKrHiUImKxKBvlNpZXan3j3OwFJmH2paKXKg.svgz" alt="M(x_1, \dots, x_n)" title="M(x_1, \dots, x_n)"></span> with the last column and the <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span>-th row removed. Note that by cyclically permuting rows <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span> to <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="13" src="https://math.fontein.de/formulae/VNmylc5SS6m0GoMzxOh2C.o19W3wV1wyQtDHlQ.svgz" alt="n - 1" title="n - 1"></span> of <span class="inline-formula"><img class="img-inline-formula img-formula" width="23" height="15" src="https://math.fontein.de/formulae/N23AF6eNmrAlqUmjiacGN5u_43aLeJC6JFMcuQ.svgz" alt="M_i" title="M_i"></span>, we obtain the matrix <span class="inline-formula"><img class="img-inline-formula img-formula" width="260" height="18" src="https://math.fontein.de/formulae/hlw_oxJEtWWDSheVj1OkrUb8UFlPWaUM6JLR6Q.svgz" alt="M(x_1, \dots, x_{i-1}, 0, x_{i+1}, \dots, x_{n-1})" title="M(x_1, \dots, x_{i-1}, 0, x_{i+1}, \dots, x_{n-1})"></span>. The permutation has sign <span class="inline-formula"><img class="img-inline-formula img-formula" width="80" height="19" src="https://math.fontein.de/formulae/7bKb1ZsMGFDWW98kV9hJ0K5IGFXbcQG2TZXp5w.svgz" alt="(-1)^{n - i + 1}" title="(-1)^{n - i + 1}"></span>, whence we see that
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="520" height="64" src="https://math.fontein.de/formulae/XK9HlUkN1.zL569tAldkkkz0oDm4UEicKsDUeA.svgz" alt="(-1)^{n+i} \det M_i = -\det M(x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_{n-1}) = -\prod_{j=1 \atop j \neq i}^{n-1} x_j." title="(-1)^{n+i} \det M_i = -\det M(x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_{n-1}) = -\prod_{j=1 \atop j \neq i}^{n-1} x_j.">
</div>
<p>
Combining everything so far, we see that
</p>
<div class="align-formula">
<img class="img-align-formula img-formula" width="421" height="158" src="https://math.fontein.de/formulae/_QAsJOdnd8OCFr4ByEEzDLalgqG7cE9f7onNnQ.svgz" alt="& \det M(x_1, \dots, x_n) \\
{}={} & \prod_{i=1}^{n-1} x_i + \sum_{j=1}^{n-1} \prod_{i=1 \atop i \neq j}^{n-1} x_i + \prod_{i=1}^n x_i + \sum_{j=1}^{n-1} \prod_{i=1 \atop i \neq j}^n x_i - \sum_{i=1}^{n-1} \prod_{j=1 \atop j \neq i}^{n-1} x_j \\
{}={} & \prod_{i=1}^n x_i + \sum_{j=1}^n \prod_{i=1 \atop i \neq j}^n x_i," title="& \det M(x_1, \dots, x_n) \\
{}={} & \prod_{i=1}^{n-1} x_i + \sum_{j=1}^{n-1} \prod_{i=1 \atop i \neq j}^{n-1} x_i + \prod_{i=1}^n x_i + \sum_{j=1}^{n-1} \prod_{i=1 \atop i \neq j}^n x_i - \sum_{i=1}^{n-1} \prod_{j=1 \atop j \neq i}^{n-1} x_j \\
{}={} & \prod_{i=1}^n x_i + \sum_{j=1}^n \prod_{i=1 \atop i \neq j}^n x_i,">
</div>
<p>
what we wanted to show.
</p>
</div>
<div class="qed-block"><span class="qed-sign"></span></div>
</div>
</div>