{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Determinants\n",
"\n",
"One of the first things that most students learn about in linear algebra is the [determinant](https://en.wikipedia.org/wiki/Determinant) of a matrix. Lots of useful formulas for 2×2 and 3×3 matrices can be expressed in terms of determinants, and determinants played a central role in linear algebra 100 years ago when most matrices were tiny.\n",
"\n",
"Nowadays, determinants are much less useful as a practical tool, although they still occasionally show up. Determinant-related formulas are also useful in proving theorems in linear algebra. The basic computational problem, however, is that the determinant formulas don't scale — for a big matrix, there is almost always a better way of computing something than using explicit determinants, cofactors, [Cramer's rule](https://en.wikipedia.org/wiki/Cramer's_rule), and other tricks useful for small matrices.\n",
"\n",
"Still, it is important to know what determinants are, and their basic properties. In 18.06, we mainly use determinants as a *conceptual* tool to help us understand eigenvalues via the [characteristic polynomial](https://en.wikipedia.org/wiki/Characteristic_polynomial) — although, again, this is not a practical *computational* tool for eigenvalues, which are nowadays computed by very different methods."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Explicit formulas, high-school version\n",
"\n",
"In high school, you may have learned some explicit formulas for determinants of small matrices.\n",
"\n",
"These formulas quickly become computational useless for larger matrices (although there is a there is still a theoretical formula we'll give at the end), but it is nice to see a few of them.\n",
"\n",
"The computer is much better at writing them down as the matrices get larger. We'll use the [Symbolics.jl package](https://github.com/JuliaSymbolics/Symbolics.jl) for symbolic algebra in Julia to write out some determinant formulas with symbols, not numbers:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"using Symbolics, LinearAlgebra"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can easily define a $3 \\times 3$ matrix of symbolic variables in $a_{i,j}$ format and take its determinant:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"\\left[\n",
"\\begin{array}{ccc}\n",
"a_{1}ˏ_1 & a_{1}ˏ_2 & a_{1}ˏ_3 \\\\\n",
"a_{2}ˏ_1 & a_{2}ˏ_2 & a_{2}ˏ_3 \\\\\n",
"a_{3}ˏ_1 & a_{3}ˏ_2 & a_{3}ˏ_3 \\\\\n",
"\\end{array}\n",
"\\right]\n",
"\\end{equation}\n"
],
"text/plain": [
"3×3 Matrix{Num}:\n",
" a[1, 1] a[1, 2] a[1, 3]\n",
" a[2, 1] a[2, 2] a[2, 3]\n",
" a[3, 1] a[3, 2] a[3, 3]"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"@variables a[1:3, 1:3]\n",
"A = collect(a)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"a_{1}ˏ_2 a_{2}ˏ_3 a_{3}ˏ_1 + a_{1}ˏ_1 a_{2}ˏ_2 a_{3}ˏ_3 + a_{1}ˏ_3 a_{2}ˏ_1 a_{3}ˏ_2 - a_{1}ˏ_3 a_{2}ˏ_2 a_{3}ˏ_1 - a_{1}ˏ_2 a_{2}ˏ_1 a_{3}ˏ_3 - a_{1}ˏ_1 a_{2}ˏ_3 a_{3}ˏ_2\n",
"\\end{equation}\n"
],
"text/plain": [
"a[1, 2]*a[2, 3]*a[3, 1] + a[1, 1]*a[2, 2]*a[3, 3] + a[1, 3]*a[2, 1]*a[3, 2] - a[1, 3]*a[2, 2]*a[3, 1] - a[1, 2]*a[2, 1]*a[3, 3] - a[1, 1]*a[2, 3]*a[3, 2]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"expand(det(A))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"… but these $a_{i,j}$ variables can be a little hard to read. Let's define some more colorful symbols:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"\\left[\n",
"\\begin{array}{cc}\n",
"a & b \\\\\n",
"🍎 & 🍌 \\\\\n",
"\\end{array}\n",
"\\right]\n",
"\\end{equation}\n"
],
"text/plain": [
"2×2 Matrix{Num}:\n",
" a b\n",
" 🍎 🍌"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"@variables a b c d 🍎 🍌 🍪 🥟 α β γ δ ♣ ♡ ♠ ♢\n",
"\n",
"A = [a b\n",
" 🍎 🍌]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here is the determinant of a $2\\times 2$ matrix:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"a 🍌 - b 🍎\n",
"\\end{equation}\n"
],
"text/plain": [
"a*🍌 - b*🍎"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(A)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"and here is $3 \\times 3$:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"\\left[\n",
"\\begin{array}{ccc}\n",
"a & b & c \\\\\n",
"🍎 & 🍌 & 🍪 \\\\\n",
"\\alpha & \\beta & \\gamma \\\\\n",
"\\end{array}\n",
"\\right]\n",
"\\end{equation}\n"
],
"text/plain": [
"3×3 Matrix{Num}:\n",
" a b c\n",
" 🍎 🍌 🍪\n",
" α β γ"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = [a b c\n",
" 🍎 🍌 🍪\n",
" α β γ]"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"a \\gamma 🍌 + c \\beta 🍎 + b \\alpha 🍪 - a \\beta 🍪 - b \\gamma 🍎 - c \\alpha 🍌\n",
"\\end{equation}\n"
],
"text/plain": [
"a*γ*🍌 + c*β*🍎 + b*α*🍪 - a*β*🍪 - b*γ*🍎 - c*α*🍌"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"expand(det(A))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice that the terms in the determinant contain **exactly one value from each row and one from each column**.\n",
"\n",
"This pattern continues for $4\\times 4$, which is rapidly getting messier:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"\\left[\n",
"\\begin{array}{cccc}\n",
"a & b & c & d \\\\\n",
"🍎 & 🍌 & 🍪 & 🥟 \\\\\n",
"\\alpha & \\beta & \\gamma & \\delta \\\\\n",
"\\clubsuit & \\heartsuit & \\spadesuit & \\diamondsuit \\\\\n",
"\\end{array}\n",
"\\right]\n",
"\\end{equation}\n"
],
"text/plain": [
"4×4 Matrix{Num}:\n",
" a b c d\n",
" 🍎 🍌 🍪 🥟\n",
" α β γ δ\n",
" ♣ ♡ ♠ ♢"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = [ a b c d\n",
" 🍎 🍌 🍪 🥟\n",
" α β γ δ\n",
" ♣ ♡ ♠ ♢]"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"d \\alpha \\spadesuit 🍌 + c \\alpha \\heartsuit 🥟 + a \\gamma \\diamondsuit 🍌 + a \\beta \\spadesuit 🥟 + b \\alpha \\diamondsuit 🍪 + c \\beta \\diamondsuit 🍎 + d \\beta \\clubsuit 🍪 + b \\gamma \\clubsuit 🥟 + b \\delta \\spadesuit 🍎 + d \\gamma \\heartsuit 🍎 + c \\delta \\clubsuit 🍌 + a \\delta \\heartsuit 🍪 - c \\delta \\heartsuit 🍎 - d \\gamma \\clubsuit 🍌 - b \\alpha \\spadesuit 🥟 - b \\delta \\clubsuit 🍪 - d \\alpha \\heartsuit 🍪 - d \\beta \\spadesuit 🍎 - a \\beta \\diamondsuit 🍪 - a \\gamma \\heartsuit 🥟 - b \\gamma \\diamondsuit 🍎 - a \\delta \\spadesuit 🍌 - c \\alpha \\diamondsuit 🍌 - c \\beta \\clubsuit 🥟\n",
"\\end{equation}\n"
],
"text/plain": [
"d*α*♠*🍌 + c*α*♡*🥟 + a*γ*♢*🍌 + a*β*♠*🥟 + b*α*♢*🍪 + c*β*♢*🍎 + d*β*♣*🍪 + b*γ*♣*🥟 + b*δ*♠*🍎 + d*γ*♡*🍎 + c*δ*♣*🍌 + a*δ*♡*🍪 - c*δ*♡*🍎 - d*γ*♣*🍌 - b*α*♠*🥟 - b*δ*♣*🍪 - d*α*♡*🍪 - d*β*♠*🍎 - a*β*♢*🍪 - a*γ*♡*🥟 - b*γ*♢*🍎 - a*δ*♠*🍌 - c*α*♢*🍌 - c*β*♣*🥟"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"expand(det(A))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"By $n=5$ these formulas have gotten ridiculous:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"\\left[\n",
"\\begin{array}{ccccc}\n",
"a_{1}ˏ_1 & a_{1}ˏ_2 & a_{1}ˏ_3 & a_{1}ˏ_4 & a_{1}ˏ_5 \\\\\n",
"a_{2}ˏ_1 & a_{2}ˏ_2 & a_{2}ˏ_3 & a_{2}ˏ_4 & a_{2}ˏ_5 \\\\\n",
"a_{3}ˏ_1 & a_{3}ˏ_2 & a_{3}ˏ_3 & a_{3}ˏ_4 & a_{3}ˏ_5 \\\\\n",
"a_{4}ˏ_1 & a_{4}ˏ_2 & a_{4}ˏ_3 & a_{4}ˏ_4 & a_{4}ˏ_5 \\\\\n",
"a_{5}ˏ_1 & a_{5}ˏ_2 & a_{5}ˏ_3 & a_{5}ˏ_4 & a_{5}ˏ_5 \\\\\n",
"\\end{array}\n",
"\\right]\n",
"\\end{equation}\n"
],
"text/plain": [
"5×5 Matrix{Num}:\n",
" a[1, 1] a[1, 2] a[1, 3] a[1, 4] a[1, 5]\n",
" a[2, 1] a[2, 2] a[2, 3] a[2, 4] a[2, 5]\n",
" a[3, 1] a[3, 2] a[3, 3] a[3, 4] a[3, 5]\n",
" a[4, 1] a[4, 2] a[4, 3] a[4, 4] a[4, 5]\n",
" a[5, 1] a[5, 2] a[5, 3] a[5, 4] a[5, 5]"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"@variables a[1:5,1:5]\n",
"A = collect(a)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"a_{1}ˏ_3 a_{2}ˏ_1 a_{3}ˏ_2 a_{4}ˏ_4 a_{5}ˏ_5 + a_{1}ˏ_2 a_{2}ˏ_4 a_{3}ˏ_5 a_{4}ˏ_3 a_{5}ˏ_1 + a_{1}ˏ_4 a_{2}ˏ_1 a_{3}ˏ_5 a_{4}ˏ_3 a_{5}ˏ_2 + a_{1}ˏ_3 a_{2}ˏ_4 a_{3}ˏ_2 a_{4}ˏ_5 a_{5}ˏ_1 + a_{1}ˏ_4 a_{2}ˏ_5 a_{3}ˏ_2 a_{4}ˏ_3 a_{5}ˏ_1 + a_{1}ˏ_5 a_{2}ˏ_4 a_{3}ˏ_1 a_{4}ˏ_3 a_{5}ˏ_2 + a_{1}ˏ_1 a_{2}ˏ_5 a_{3}ˏ_4 a_{4}ˏ_3 a_{5}ˏ_2 + a_{1}ˏ_1 a_{2}ˏ_2 a_{3}ˏ_4 a_{4}ˏ_5 a_{5}ˏ_3 + a_{1}ˏ_4 a_{2}ˏ_2 a_{3}ˏ_1 a_{4}ˏ_3 a_{5}ˏ_5 + a_{1}ˏ_5 a_{2}ˏ_2 a_{3}ˏ_3 a_{4}ˏ_1 a_{5}ˏ_4 + a_{1}ˏ_4 a_{2}ˏ_2 a_{3}ˏ_5 a_{4}ˏ_1 a_{5}ˏ_3 + a_{1}ˏ_1 a_{2}ˏ_2 a_{3}ˏ_3 a_{4}ˏ_4 a_{5}ˏ_5 + a_{1}ˏ_3 a_{2}ˏ_1 a_{3}ˏ_4 a_{4}ˏ_5 a_{5}ˏ_2 + a_{1}ˏ_2 a_{2}ˏ_3 a_{3}ˏ_5 a_{4}ˏ_1 a_{5}ˏ_4 + a_{1}ˏ_5 a_{2}ˏ_1 a_{3}ˏ_2 a_{4}ˏ_3 a_{5}ˏ_4 + a_{1}ˏ_2 a_{2}ˏ_5 a_{3}ˏ_1 a_{4}ˏ_3 a_{5}ˏ_4 + a_{1}ˏ_5 a_{2}ˏ_1 a_{3}ˏ_4 a_{4}ˏ_2 a_{5}ˏ_3 + a_{1}ˏ_5 a_{2}ˏ_1 a_{3}ˏ_3 a_{4}ˏ_4 a_{5}ˏ_2 + a_{1}ˏ_2 a_{2}ˏ_1 a_{3}ˏ_3 a_{4}ˏ_5 a_{5}ˏ_4 + a_{1}ˏ_2 a_{2}ˏ_1 a_{3}ˏ_5 a_{4}ˏ_4 a_{5}ˏ_3 + a_{1}ˏ_5 a_{2}ˏ_3 a_{3}ˏ_1 a_{4}ˏ_2 a_{5}ˏ_4 + a_{1}ˏ_1 a_{2}ˏ_4 a_{3}ˏ_3 a_{4}ˏ_5 a_{5}ˏ_2 + a_{1}ˏ_3 a_{2}ˏ_2 a_{3}ˏ_1 a_{4}ˏ_5 a_{5}ˏ_4 + a_{1}ˏ_4 a_{2}ˏ_3 a_{3}ˏ_5 a_{4}ˏ_2 a_{5}ˏ_1 + a_{1}ˏ_1 a_{2}ˏ_3 a_{3}ˏ_5 a_{4}ˏ_4 a_{5}ˏ_2 + a_{1}ˏ_1 a_{2}ˏ_3 a_{3}ˏ_4 a_{4}ˏ_2 a_{5}ˏ_5 + a_{1}ˏ_2 a_{2}ˏ_4 a_{3}ˏ_1 a_{4}ˏ_5 a_{5}ˏ_3 + a_{1}ˏ_3 a_{2}ˏ_5 a_{3}ˏ_1 a_{4}ˏ_4 a_{5}ˏ_2 + a_{1}ˏ_1 a_{2}ˏ_5 a_{3}ˏ_3 a_{4}ˏ_2 a_{5}ˏ_4 + a_{1}ˏ_3 a_{2}ˏ_2 a_{3}ˏ_4 a_{4}ˏ_1 a_{5}ˏ_5 + a_{1}ˏ_4 a_{2}ˏ_5 a_{3}ˏ_3 a_{4}ˏ_1 a_{5}ˏ_2 + a_{1}ˏ_5 a_{2}ˏ_4 a_{3}ˏ_2 a_{4}ˏ_1 a_{5}ˏ_3 + a_{1}ˏ_2 a_{2}ˏ_3 a_{3}ˏ_1 a_{4}ˏ_4 a_{5}ˏ_5 + a_{1}ˏ_4 a_{2}ˏ_3 a_{3}ˏ_2 a_{4}ˏ_1 a_{5}ˏ_5 + a_{1}ˏ_4 a_{2}ˏ_1 a_{3}ˏ_2 a_{4}ˏ_5 a_{5}ˏ_3 + a_{1}ˏ_1 a_{2}ˏ_4 a_{3}ˏ_2 a_{4}ˏ_3 a_{5}ˏ_5 + a_{1}ˏ_3 a_{2}ˏ_4 a_{3}ˏ_1 a_{4}ˏ_2 a_{5}ˏ_5 + a_{1}ˏ_3 a_{2}ˏ_4 a_{3}ˏ_5 a_{4}ˏ_1 a_{5}ˏ_2 + a_{1}ˏ_2 a_{2}ˏ_1 a_{3}ˏ_4 a_{4}ˏ_3 a_{5}ˏ_5 + a_{1}ˏ_5 a_{2}ˏ_2 a_{3}ˏ_4 a_{4}ˏ_3 a_{5}ˏ_1 + a_{1}ˏ_1 a_{2}ˏ_4 a_{3}ˏ_5 a_{4}ˏ_2 a_{5}ˏ_3 + a_{1}ˏ_3 a_{2}ˏ_1 a_{3}ˏ_5 a_{4}ˏ_2 a_{5}ˏ_4 + a_{1}ˏ_4 a_{2}ˏ_3 a_{3}ˏ_1 a_{4}ˏ_5 a_{5}ˏ_2 + a_{1}ˏ_2 a_{2}ˏ_4 a_{3}ˏ_3 a_{4}ˏ_1 a_{5}ˏ_5 + a_{1}ˏ_1 a_{2}ˏ_2 a_{3}ˏ_5 a_{4}ˏ_3 a_{5}ˏ_4 + a_{1}ˏ_4 a_{2}ˏ_5 a_{3}ˏ_1 a_{4}ˏ_2 a_{5}ˏ_3 + a_{1}ˏ_5 a_{2}ˏ_2 a_{3}ˏ_1 a_{4}ˏ_4 a_{5}ˏ_3 + a_{1}ˏ_5 a_{2}ˏ_3 a_{3}ˏ_2 a_{4}ˏ_4 a_{5}ˏ_1 + a_{1}ˏ_3 a_{2}ˏ_5 a_{3}ˏ_2 a_{4}ˏ_1 a_{5}ˏ_4 + a_{1}ˏ_2 a_{2}ˏ_5 a_{3}ˏ_4 a_{4}ˏ_1 a_{5}ˏ_3 + a_{1}ˏ_4 a_{2}ˏ_1 a_{3}ˏ_3 a_{4}ˏ_2 a_{5}ˏ_5 + a_{1}ˏ_2 a_{2}ˏ_3 a_{3}ˏ_4 a_{4}ˏ_5 a_{5}ˏ_1 + a_{1}ˏ_2 a_{2}ˏ_5 a_{3}ˏ_3 a_{4}ˏ_4 a_{5}ˏ_1 + a_{1}ˏ_3 a_{2}ˏ_5 a_{3}ˏ_4 a_{4}ˏ_2 a_{5}ˏ_1 + a_{1}ˏ_1 a_{2}ˏ_3 a_{3}ˏ_2 a_{4}ˏ_5 a_{5}ˏ_4 + a_{1}ˏ_4 a_{2}ˏ_2 a_{3}ˏ_3 a_{4}ˏ_5 a_{5}ˏ_1 + a_{1}ˏ_5 a_{2}ˏ_3 a_{3}ˏ_4 a_{4}ˏ_1 a_{5}ˏ_2 + a_{1}ˏ_3 a_{2}ˏ_2 a_{3}ˏ_5 a_{4}ˏ_4 a_{5}ˏ_1 + a_{1}ˏ_1 a_{2}ˏ_5 a_{3}ˏ_2 a_{4}ˏ_4 a_{5}ˏ_3 + a_{1}ˏ_5 a_{2}ˏ_4 a_{3}ˏ_3 a_{4}ˏ_2 a_{5}ˏ_1 - a_{1}ˏ_1 a_{2}ˏ_2 a_{3}ˏ_3 a_{4}ˏ_5 a_{5}ˏ_4 - a_{1}ˏ_4 a_{2}ˏ_2 a_{3}ˏ_5 a_{4}ˏ_3 a_{5}ˏ_1 - a_{1}ˏ_3 a_{2}ˏ_2 a_{3}ˏ_4 a_{4}ˏ_5 a_{5}ˏ_1 - a_{1}ˏ_2 a_{2}ˏ_5 a_{3}ˏ_4 a_{4}ˏ_3 a_{5}ˏ_1 - a_{1}ˏ_2 a_{2}ˏ_1 a_{3}ˏ_5 a_{4}ˏ_3 a_{5}ˏ_4 - a_{1}ˏ_4 a_{2}ˏ_1 a_{3}ˏ_2 a_{4}ˏ_3 a_{5}ˏ_5 - a_{1}ˏ_3 a_{2}ˏ_1 a_{3}ˏ_4 a_{4}ˏ_2 a_{5}ˏ_5 - a_{1}ˏ_5 a_{2}ˏ_2 a_{3}ˏ_3 a_{4}ˏ_4 a_{5}ˏ_1 - a_{1}ˏ_5 a_{2}ˏ_2 a_{3}ˏ_1 a_{4}ˏ_3 a_{5}ˏ_4 - a_{1}ˏ_3 a_{2}ˏ_2 a_{3}ˏ_5 a_{4}ˏ_1 a_{5}ˏ_4 - a_{1}ˏ_4 a_{2}ˏ_1 a_{3}ˏ_5 a_{4}ˏ_2 a_{5}ˏ_3 - a_{1}ˏ_5 a_{2}ˏ_1 a_{3}ˏ_3 a_{4}ˏ_2 a_{5}ˏ_4 - a_{1}ˏ_4 a_{2}ˏ_2 a_{3}ˏ_3 a_{4}ˏ_1 a_{5}ˏ_5 - a_{1}ˏ_1 a_{2}ˏ_4 a_{3}ˏ_2 a_{4}ˏ_5 a_{5}ˏ_3 - a_{1}ˏ_1 a_{2}ˏ_5 a_{3}ˏ_4 a_{4}ˏ_2 a_{5}ˏ_3 - a_{1}ˏ_3 a_{2}ˏ_4 a_{3}ˏ_5 a_{4}ˏ_2 a_{5}ˏ_1 - a_{1}ˏ_5 a_{2}ˏ_3 a_{3}ˏ_1 a_{4}ˏ_4 a_{5}ˏ_2 - a_{1}ˏ_1 a_{2}ˏ_3 a_{3}ˏ_4 a_{4}ˏ_5 a_{5}ˏ_2 - a_{1}ˏ_2 a_{2}ˏ_1 a_{3}ˏ_3 a_{4}ˏ_4 a_{5}ˏ_5 - a_{1}ˏ_1 a_{2}ˏ_5 a_{3}ˏ_2 a_{4}ˏ_3 a_{5}ˏ_4 - a_{1}ˏ_3 a_{2}ˏ_4 a_{3}ˏ_2 a_{4}ˏ_1 a_{5}ˏ_5 - a_{1}ˏ_1 a_{2}ˏ_4 a_{3}ˏ_3 a_{4}ˏ_2 a_{5}ˏ_5 - a_{1}ˏ_5 a_{2}ˏ_3 a_{3}ˏ_2 a_{4}ˏ_1 a_{5}ˏ_4 - a_{1}ˏ_5 a_{2}ˏ_1 a_{3}ˏ_2 a_{4}ˏ_4 a_{5}ˏ_3 - a_{1}ˏ_5 a_{2}ˏ_4 a_{3}ˏ_2 a_{4}ˏ_3 a_{5}ˏ_1 - a_{1}ˏ_1 a_{2}ˏ_3 a_{3}ˏ_2 a_{4}ˏ_4 a_{5}ˏ_5 - a_{1}ˏ_2 a_{2}ˏ_4 a_{3}ˏ_5 a_{4}ˏ_1 a_{5}ˏ_3 - a_{1}ˏ_4 a_{2}ˏ_5 a_{3}ˏ_3 a_{4}ˏ_2 a_{5}ˏ_1 - a_{1}ˏ_5 a_{2}ˏ_4 a_{3}ˏ_1 a_{4}ˏ_2 a_{5}ˏ_3 - a_{1}ˏ_1 a_{2}ˏ_2 a_{3}ˏ_4 a_{4}ˏ_3 a_{5}ˏ_5 - a_{1}ˏ_4 a_{2}ˏ_5 a_{3}ˏ_1 a_{4}ˏ_3 a_{5}ˏ_2 - a_{1}ˏ_4 a_{2}ˏ_3 a_{3}ˏ_1 a_{4}ˏ_2 a_{5}ˏ_5 - a_{1}ˏ_3 a_{2}ˏ_1 a_{3}ˏ_2 a_{4}ˏ_5 a_{5}ˏ_4 - a_{1}ˏ_5 a_{2}ˏ_4 a_{3}ˏ_3 a_{4}ˏ_1 a_{5}ˏ_2 - a_{1}ˏ_3 a_{2}ˏ_5 a_{3}ˏ_4 a_{4}ˏ_1 a_{5}ˏ_2 - a_{1}ˏ_3 a_{2}ˏ_5 a_{3}ˏ_2 a_{4}ˏ_4 a_{5}ˏ_1 - a_{1}ˏ_3 a_{2}ˏ_1 a_{3}ˏ_5 a_{4}ˏ_4 a_{5}ˏ_2 - a_{1}ˏ_2 a_{2}ˏ_3 a_{3}ˏ_5 a_{4}ˏ_4 a_{5}ˏ_1 - a_{1}ˏ_2 a_{2}ˏ_5 a_{3}ˏ_1 a_{4}ˏ_4 a_{5}ˏ_3 - a_{1}ˏ_3 a_{2}ˏ_5 a_{3}ˏ_1 a_{4}ˏ_2 a_{5}ˏ_4 - a_{1}ˏ_4 a_{2}ˏ_3 a_{3}ˏ_5 a_{4}ˏ_1 a_{5}ˏ_2 - a_{1}ˏ_4 a_{2}ˏ_2 a_{3}ˏ_1 a_{4}ˏ_5 a_{5}ˏ_3 - a_{1}ˏ_4 a_{2}ˏ_5 a_{3}ˏ_2 a_{4}ˏ_1 a_{5}ˏ_3 - a_{1}ˏ_2 a_{2}ˏ_3 a_{3}ˏ_1 a_{4}ˏ_5 a_{5}ˏ_4 - a_{1}ˏ_1 a_{2}ˏ_5 a_{3}ˏ_3 a_{4}ˏ_4 a_{5}ˏ_2 - a_{1}ˏ_4 a_{2}ˏ_3 a_{3}ˏ_2 a_{4}ˏ_5 a_{5}ˏ_1 - a_{1}ˏ_2 a_{2}ˏ_1 a_{3}ˏ_4 a_{4}ˏ_5 a_{5}ˏ_3 - a_{1}ˏ_3 a_{2}ˏ_4 a_{3}ˏ_1 a_{4}ˏ_5 a_{5}ˏ_2 - a_{1}ˏ_5 a_{2}ˏ_3 a_{3}ˏ_4 a_{4}ˏ_2 a_{5}ˏ_1 - a_{1}ˏ_2 a_{2}ˏ_4 a_{3}ˏ_1 a_{4}ˏ_3 a_{5}ˏ_5 - a_{1}ˏ_1 a_{2}ˏ_3 a_{3}ˏ_5 a_{4}ˏ_2 a_{5}ˏ_4 - a_{1}ˏ_5 a_{2}ˏ_2 a_{3}ˏ_4 a_{4}ˏ_1 a_{5}ˏ_3 - a_{1}ˏ_4 a_{2}ˏ_1 a_{3}ˏ_3 a_{4}ˏ_5 a_{5}ˏ_2 - a_{1}ˏ_1 a_{2}ˏ_4 a_{3}ˏ_5 a_{4}ˏ_3 a_{5}ˏ_2 - a_{1}ˏ_1 a_{2}ˏ_2 a_{3}ˏ_5 a_{4}ˏ_4 a_{5}ˏ_3 - a_{1}ˏ_2 a_{2}ˏ_4 a_{3}ˏ_3 a_{4}ˏ_5 a_{5}ˏ_1 - a_{1}ˏ_2 a_{2}ˏ_3 a_{3}ˏ_4 a_{4}ˏ_1 a_{5}ˏ_5 - a_{1}ˏ_5 a_{2}ˏ_1 a_{3}ˏ_4 a_{4}ˏ_3 a_{5}ˏ_2 - a_{1}ˏ_2 a_{2}ˏ_5 a_{3}ˏ_3 a_{4}ˏ_1 a_{5}ˏ_4 - a_{1}ˏ_3 a_{2}ˏ_2 a_{3}ˏ_1 a_{4}ˏ_4 a_{5}ˏ_5\n",
"\\end{equation}\n"
],
"text/plain": [
"a[1, 3]*a[2, 1]*a[3, 2]*a[4, 4]*a[5, 5] + a[1, 2]*a[2, 4]*a[3, 5]*a[4, 3]*a[5, 1] + a[1, 4]*a[2, 1]*a[3, 5]*a[4, 3]*a[5, 2] + a[1, 3]*a[2, 4]*a[3, 2]*a[4, 5]*a[5, 1] + a[1, 4]*a[2, 5]*a[3, 2]*a[4, 3]*a[5, 1] + a[1, 5]*a[2, 4]*a[3, 1]*a[4, 3]*a[5, 2] + a[1, 1]*a[2, 5]*a[3, 4]*a[4, 3]*a[5, 2] + a[1, 1]*a[2, 2]*a[3, 4]*a[4, 5]*a[5, 3] + a[1, 4]*a[2, 2]*a[3, 1]*a[4, 3]*a[5, 5] + a[1, 5]*a[2, 2]*a[3, 3]*a[4, 1]*a[5, 4] + a[1, 4]*a[2, 2]*a[3, 5]*a[4, 1]*a[5, 3] + a[1, 1]*a[2, 2]*a[3, 3]*a[4, 4]*a[5, 5] + a[1, 3]*a[2, 1]*a[3, 4]*a[4, 5]*a[5, 2] + a[1, 2]*a[2, 3]*a[3, 5]*a[4, 1]*a[5, 4] + a[1, 5]*a[2, 1]*a[3, 2]*a[4, 3]*a[5, 4] + a[1, 2]*a[2, 5]*a[3, 1]*a[4, 3]*a[5, 4] + a[1, 5]*a[2, 1]*a[3, 4]*a[4, 2]*a[5, 3] + a[1, 5]*a[2, 1]*a[3, 3]*a[4, 4]*a[5, 2] + a[1, 2]*a[2, 1]*a[3, 3]*a[4, 5]*a[5, 4] + a[1, 2]*a[2, 1]*a[3, 5]*a[4, 4]*a[5, 3] + a[1, 5]*a[2, 3]*a[3, 1]*a[4, 2]*a[5, 4] + a[1, 1]*a[2, 4]*a[3, 3]*a[4, 5]*a[5, 2] + a[1, 3]*a[2, 2]*a[3, 1]*a[4, 5]*a[5, 4] + a[1, 4]*a[2, 3]*a[3, 5]*a[4, 2]*a[5, 1] + a[1, 1]*a[2, 3]*a[3, 5]*a[4, 4]*a[5, 2] + a[1, 1]*a[2, 3]*a[3, 4]*a[4, 2]*a[5, 5] + a[1, 2]*a[2, 4]*a[3, 1]*a[4, 5]*a[5, 3] + a[1, 3]*a[2, 5]*a[3, 1]*a[4, 4]*a[5, 2] + a[1, 1]*a[2, 5]*a[3, 3]*a[4, 2]*a[5, 4] + a[1, 3]*a[2, 2]*a[3, 4]*a[4, 1]*a[5, 5] + a[1, 4]*a[2, 5]*a[3, 3]*a[4, 1]*a[5, 2] + a[1, 5]*a[2, 4]*a[3, 2]*a[4, 1]*a[5, 3] + a[1, 2]*a[2, 3]*a[3, 1]*a[4, 4]*a[5, 5] + a[1, 4]*a[2, 3]*a[3, 2]*a[4, 1]*a[5, 5] + a[1, 4]*a[2, 1]*a[3, 2]*a[4, 5]*a[5, 3] + a[1, 1]*a[2, 4]*a[3, 2]*a[4, 3]*a[5, 5] + a[1, 3]*a[2, 4]*a[3, 1]*a[4, 2]*a[5, 5] + a[1, 3]*a[2, 4]*a[3, 5]*a[4, 1]*a[5, 2] + a[1, 2]*a[2, 1]*a[3, 4]*a[4, 3]*a[5, 5] + a[1, 5]*a[2, 2]*a[3, 4]*a[4, 3]*a[5, 1] + a[1, 1]*a[2, 4]*a[3, 5]*a[4, 2]*a[5, 3] + a[1, 3]*a[2, 1]*a[3, 5]*a[4, 2]*a[5, 4] + a[1, 4]*a[2, 3]*a[3, 1]*a[4, 5]*a[5, 2] + a[1, 2]*a[2, 4]*a[3, 3]*a[4, 1]*a[5, 5] + a[1, 1]*a[2, 2]*a[3, 5]*a[4, 3]*a[5, 4] + a[1, 4]*a[2, 5]*a[3, 1]*a[4, 2]*a[5, 3] + a[1, 5]*a[2, 2]*a[3, 1]*a[4, 4]*a[5, 3] + a[1, 5]*a[2, 3]*a[3, 2]*a[4, 4]*a[5, 1] + a[1, 3]*a[2, 5]*a[3, 2]*a[4, 1]*a[5, 4] + a[1, 2]*a[2, 5]*a[3, 4]*a[4, 1]*a[5, 3] + a[1, 4]*a[2, 1]*a[3, 3]*a[4, 2]*a[5, 5] + a[1, 2]*a[2, 3]*a[3, 4]*a[4, 5]*a[5, 1] + a[1, 2]*a[2, 5]*a[3, 3]*a[4, 4]*a[5, 1] + a[1, 3]*a[2, 5]*a[3, 4]*a[4, 2]*a[5, 1] + a[1, 1]*a[2, 3]*a[3, 2]*a[4, 5]*a[5, 4] + a[1, 4]*a[2, 2]*a[3, 3]*a[4, 5]*a[5, 1] + a[1, 5]*a[2, 3]*a[3, 4]*a[4, 1]*a[5, 2] + a[1, 3]*a[2, 2]*a[3, 5]*a[4, 4]*a[5, 1] + a[1, 1]*a[2, 5]*a[3, 2]*a[4, 4]*a[5, 3] + a[1, 5]*a[2, 4]*a[3, 3]*a[4, 2]*a[5, 1] - a[1, 1]*a[2, 2]*a[3, 3]*a[4, 5]*a[5, 4] - a[1, 4]*a[2, 2]*a[3, 5]*a[4, 3]*a[5, 1] - a[1, 3]*a[2, 2]*a[3, 4]*a[4, 5]*a[5, 1] - a[1, 2]*a[2, 5]*a[3, 4]*a[4, 3]*a[5, 1] - a[1, 2]*a[2, 1]*a[3, 5]*a[4, 3]*a[5, 4] - a[1, 4]*a[2, 1]*a[3, 2]*a[4, 3]*a[5, 5] - a[1, 3]*a[2, 1]*a[3, 4]*a[4, 2]*a[5, 5] - a[1, 5]*a[2, 2]*a[3, 3]*a[4, 4]*a[5, 1] - a[1, 5]*a[2, 2]*a[3, 1]*a[4, 3]*a[5, 4] - a[1, 3]*a[2, 2]*a[3, 5]*a[4, 1]*a[5, 4] - a[1, 4]*a[2, 1]*a[3, 5]*a[4, 2]*a[5, 3] - a[1, 5]*a[2, 1]*a[3, 3]*a[4, 2]*a[5, 4] - a[1, 4]*a[2, 2]*a[3, 3]*a[4, 1]*a[5, 5] - a[1, 1]*a[2, 4]*a[3, 2]*a[4, 5]*a[5, 3] - a[1, 1]*a[2, 5]*a[3, 4]*a[4, 2]*a[5, 3] - a[1, 3]*a[2, 4]*a[3, 5]*a[4, 2]*a[5, 1] - a[1, 5]*a[2, 3]*a[3, 1]*a[4, 4]*a[5, 2] - a[1, 1]*a[2, 3]*a[3, 4]*a[4, 5]*a[5, 2] - a[1, 2]*a[2, 1]*a[3, 3]*a[4, 4]*a[5, 5] - a[1, 1]*a[2, 5]*a[3, 2]*a[4, 3]*a[5, 4] - a[1, 3]*a[2, 4]*a[3, 2]*a[4, 1]*a[5, 5] - a[1, 1]*a[2, 4]*a[3, 3]*a[4, 2]*a[5, 5] - a[1, 5]*a[2, 3]*a[3, 2]*a[4, 1]*a[5, 4] - a[1, 5]*a[2, 1]*a[3, 2]*a[4, 4]*a[5, 3] - a[1, 5]*a[2, 4]*a[3, 2]*a[4, 3]*a[5, 1] - a[1, 1]*a[2, 3]*a[3, 2]*a[4, 4]*a[5, 5] - a[1, 2]*a[2, 4]*a[3, 5]*a[4, 1]*a[5, 3] - a[1, 4]*a[2, 5]*a[3, 3]*a[4, 2]*a[5, 1] - a[1, 5]*a[2, 4]*a[3, 1]*a[4, 2]*a[5, 3] - a[1, 1]*a[2, 2]*a[3, 4]*a[4, 3]*a[5, 5] - a[1, 4]*a[2, 5]*a[3, 1]*a[4, 3]*a[5, 2] - a[1, 4]*a[2, 3]*a[3, 1]*a[4, 2]*a[5, 5] - a[1, 3]*a[2, 1]*a[3, 2]*a[4, 5]*a[5, 4] - a[1, 5]*a[2, 4]*a[3, 3]*a[4, 1]*a[5, 2] - a[1, 3]*a[2, 5]*a[3, 4]*a[4, 1]*a[5, 2] - a[1, 3]*a[2, 5]*a[3, 2]*a[4, 4]*a[5, 1] - a[1, 3]*a[2, 1]*a[3, 5]*a[4, 4]*a[5, 2] - a[1, 2]*a[2, 3]*a[3, 5]*a[4, 4]*a[5, 1] - a[1, 2]*a[2, 5]*a[3, 1]*a[4, 4]*a[5, 3] - a[1, 3]*a[2, 5]*a[3, 1]*a[4, 2]*a[5, 4] - a[1, 4]*a[2, 3]*a[3, 5]*a[4, 1]*a[5, 2] - a[1, 4]*a[2, 2]*a[3, 1]*a[4, 5]*a[5, 3] - a[1, 4]*a[2, 5]*a[3, 2]*a[4, 1]*a[5, 3] - a[1, 2]*a[2, 3]*a[3, 1]*a[4, 5]*a[5, 4] - a[1, 1]*a[2, 5]*a[3, 3]*a[4, 4]*a[5, 2] - a[1, 4]*a[2, 3]*a[3, 2]*a[4, 5]*a[5, 1] - a[1, 2]*a[2, 1]*a[3, 4]*a[4, 5]*a[5, 3] - a[1, 3]*a[2, 4]*a[3, 1]*a[4, 5]*a[5, 2] - a[1, 5]*a[2, 3]*a[3, 4]*a[4, 2]*a[5, 1] - a[1, 2]*a[2, 4]*a[3, 1]*a[4, 3]*a[5, 5] - a[1, 1]*a[2, 3]*a[3, 5]*a[4, 2]*a[5, 4] - a[1, 5]*a[2, 2]*a[3, 4]*a[4, 1]*a[5, 3] - a[1, 4]*a[2, 1]*a[3, 3]*a[4, 5]*a[5, 2] - a[1, 1]*a[2, 4]*a[3, 5]*a[4, 3]*a[5, 2] - a[1, 1]*a[2, 2]*a[3, 5]*a[4, 4]*a[5, 3] - a[1, 2]*a[2, 4]*a[3, 3]*a[4, 5]*a[5, 1] - a[1, 2]*a[2, 3]*a[3, 4]*a[4, 1]*a[5, 5] - a[1, 5]*a[2, 1]*a[3, 4]*a[4, 3]*a[5, 2] - a[1, 2]*a[2, 5]*a[3, 3]*a[4, 1]*a[5, 4] - a[1, 3]*a[2, 2]*a[3, 1]*a[4, 4]*a[5, 5]"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"expand(det(A))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In fact, the number of terms in these formulas **increases faster than exponentially** with $n$, as we shall see. If we want to use determinants at all, we want a better way to think about them (and compute them) if possible."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"\\left[\n",
"\\begin{array}{c}\n",
"a \\\\\n",
"\\end{array}\n",
"\\right]\n",
"\\end{equation}\n"
],
"text/plain": [
"1-element Vector{Num}:\n",
" a"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"@variables a # make this back to an ordinary scalar variable"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Expectation: Singular = Zero determinant\n",
"\n",
"The property that most students learn about determinants of 2×2 and 3×3 is this: **given a square matrix A, the determinant det(A) is some number that is zero if and only if the matrix is singular**.\n",
"\n",
"For example, the following matrix is not singular, and its determinant (`det(A)` in Julia) is nonzero:"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"-2.0"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = [1 3\n",
" 2 4]\n",
"det(A)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(You may even remember the formula for the 2×2 determinant: $1 \\times 4 - 3 \\times 2 = -2$.\n",
"\n",
"But this matrix is singular (the second column is twice the first), and so its determinant is zero:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.0"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = [1 2\n",
" 2 4]\n",
"det(A)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"* By the way, many authors, including Strang's book, use the abbreviated notation $|A| = \\det A$. I won't use this notation here, mainly because I don't think the determinant is important enough anymore to deserve its own punctuation. Anyway, $|A|$ looks too much like an absolute value, even though the determinant can have any sign. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## A lucky guess for the determinant\n",
"\n",
"In 18.06, we know have another way to check whether a matrix is zero: perform Gaussian elimination, and then **check whether any pivots (diagonal entries of U) are zero**.\n",
"\n",
"But this gives us an obvious way to construct a single determinant-like number: **just multiply the pivots together**, and the result will be zero if and only if the matrix is singular.\n",
"\n",
"In fact, this intuition turns out to be *almost* exactly the right guess:\n",
"\n",
"* The **determinant is ± the product of the pivots**, with a minus sign if elimination involved an *odd* number of row swaps and a plus sign if there were an *even* number of swaps (including zero swaps)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can check it for a random matrix:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4.225997606151304"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = randn(5,5)\n",
"det(A)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Matrix{Float64}:\n",
" -0.767285 -0.229022 0.124838 0.427701 0.35248\n",
" 0.0 -0.749302 1.04241 2.72733 0.929833\n",
" 0.0 0.0 -0.567867 -2.57839 -1.36299\n",
" 0.0 0.0 0.0 7.0929 7.13283\n",
" 0.0 0.0 0.0 0.0 -1.82493"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"L,U = lu(A, NoPivot()) # LU without row swaps\n",
"U"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4.225997606151305"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"prod(diag(U)) # the product of the diagonal elements of U"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that this matches `det(A)` (up to roundoff errors in the last few digits)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This immediately gives you a hint of why the determinant is not such a useful computational tool as you might have thought:\n",
"\n",
"* The most efficient way to compute a determinant, in general, is to do Gaussian elimination and then multiply the pivots together.\n",
"\n",
"* Once you have done elimination, you *already* know whether the matrix is singular and you can *already* solve $Ax=b$ efficiently, so the determinant is mostly superfluous.\n",
"\n",
"We'll discuss some actual determinant applications later.\n",
"\n",
"Although we *could* use the \"product of the pivots\" as the definition of the determinant (at least for matrices), it is more typical to **build up the definition of the determinant from more basic properties**, and to get the product of the pivots as a *consequence*. We will do that now."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Defining properties of the determinant\n",
"\n",
"The following three properties are actually sufficient to *uniquely define* the determinant of any matrix, and are taken from [Strang's Introduction to Linear Algebra](http://math.mit.edu/~gs/linearalgebra/), section 5.1.\n",
"\n",
"Therefore, we don't *derive* these properties: they are [axioms](https://en.wikipedia.org/wiki/Axiom) that serve to define the determinant operation."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. det(I) = 1\n",
"\n",
"It is clear that the identity matrix $I$ is not singular, and all its pivots are 1. A reasonable starting point for defining determinants, therefore, is to require:\n",
"\n",
"* $\\det I = 1$ for any $m \\times m$ identity matrix I (any $m$).\n",
"\n",
"For example:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Diagonal{Int64, Vector{Int64}}:\n",
" 1 ⋅ ⋅ ⋅ ⋅\n",
" ⋅ 1 ⋅ ⋅ ⋅\n",
" ⋅ ⋅ 1 ⋅ ⋅\n",
" ⋅ ⋅ ⋅ 1 ⋅\n",
" ⋅ ⋅ ⋅ ⋅ 1"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"I₅ = I(5) * 1"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(I₅)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Sign flips under row exchange\n",
"\n",
"The second key property is:\n",
"\n",
"* If you **swap two rows** in a matrix, the **determinant flips sign**.\n",
"\n",
"It's easy to see this for the high-school $2\\times 2$ matrix formula:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"a 🍌 - b 🍎\n",
"\\end{equation}\n"
],
"text/plain": [
"a*🍌 - b*🍎"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det([a b\n",
" 🍎 🍌])"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"\\begin{equation}\n",
"b 🍎 - a 🍌\n",
"\\end{equation}\n"
],
"text/plain": [
"b*🍎 - a*🍌"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det([🍎 🍌\n",
" a b])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Or for the identity matrix, where swapping the first two rows gives a determinant $-1$:"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Matrix{Int64}:\n",
" 0 1 0 0 0\n",
" 1 0 0 0 0\n",
" 0 0 1 0 0\n",
" 0 0 0 1 0\n",
" 0 0 0 0 1"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"I₅_swapped = I₅[ [2,1,3,4,5], : ]"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"-1.0"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(I₅_swapped)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As another example, let's try it with a random $5 \\times 5$ matrix $A$:"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Matrix{Int64}:\n",
" 1 -2 -1 1 -1\n",
" 1 1 1 3 3\n",
" -1 2 -1 3 3\n",
" 2 -2 -1 2 1\n",
" -2 0 -2 -2 0"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = rand(-3:3, 5,5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Swapping the first two rows gives the matrix $B$:"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Matrix{Int64}:\n",
" 1 1 1 3 3\n",
" 1 -2 -1 1 -1\n",
" -1 2 -1 3 3\n",
" 2 -2 -1 2 1\n",
" -2 0 -2 -2 0"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"B = A[ [2,1,3,4,5], : ]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Hence the determinants are equal and opposite:"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(24.0, -24.0)"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(A), det(B)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(Up to roundoff errors, of course.)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Linearity in any individual row\n",
"\n",
"The determinant will *not* be a linear operation on the whole matrix: $\\det(A+B) \\ne \\det A + \\det B$!! But, we *would* like it to be linear with respect to **operations on individual rows**.\n",
"\n",
"This means two things:\n",
"\n",
"### Scaling rows\n",
"\n",
"* If we **multiply a row by a scalar α**, then the **determinant multiplies by α**.\n",
"\n",
"This axiom actually makes a lot of sense if you think about the example of the identity matrix. Multiplying the first row of $I$ by $\\alpha$ leads to the matrix:\n",
"\n",
"$$\n",
"\\begin{pmatrix}\n",
"\\alpha & 0 & 0 & 0 & \\cdots \\\\\n",
" 0 & 1 & 0 & 0 & \\cdots \\\\\n",
" 0 & 0 & 1 & 0 & \\cdots \\\\\n",
" 0 & 0 & 0 & 1 & \\cdots \\\\\n",
" \\vdots & \\vdots & \\vdots & \\vdots & \\ddots \\\\\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"The determinant of this matrix is exactly $\\alpha$! As $\\alpha \\to 0$, this matrix becomes singular, and the determinant goes to zero at the same rate. It is also consistent with our \"product of the pivots\" intuitive guess above, because the pivots here are $(\\alpha, 1, 1, \\cdots)$.\n",
"\n",
"\n",
"We can also try this with our random matrix $A$ from above. Let's multiply the second row by 2:"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Matrix{Int64}:\n",
" 1 -2 -1 1 -1\n",
" 2 2 2 6 6\n",
" -1 2 -1 3 3\n",
" 2 -2 -1 2 1\n",
" -2 0 -2 -2 0"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"C = copy(A)\n",
"C[2,:] = 2*A[2,:]\n",
"C"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(24.0, 48.0)"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(A), det(C)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As expected, the determinant doubles.\n",
"\n",
"As a consequence of this, if you multiply an *entire* $m\\times m$ matrix $A$ by $\\alpha$, we obtain:\n",
"\n",
"* $\\det(\\alpha A) = \\alpha^m \\det A$\n",
"\n",
"This is *not* an axiom, it is a *consequence* of the axiom above: we pick up a factor of $\\alpha$ for each row that we scale.\n",
"\n",
"For our $5 \\times 5$ matrix $A$, this means that $\\det(2A) = 2^5 \\det A = 32 \\det A$:"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"32.0"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(2A) / det(A)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If we think back to our high-school formulas, this is consistent — the determinant terms each had exactly **one factor from each row**. So, if we multiply any row by $\\alpha$, then the determinant multiples by $\\alpha$, and if we multiply *all* of the rows by $\\alpha$ then we get a factor of $\\alpha^m$. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Adding a row vector to a row\n",
"\n",
"There is a second property of linearity, corresponding to vector addition:\n",
"\n",
"* If we **add a row vector $r$** to a row of $A$, then the determinant becomes $\\det(A) + \\det(A')$, where $A'$ is the matrix with that row **replaced by** $r$ (with **other rows unchanged**).\n",
"\n",
"This is easier to explain with an example:\n",
"\n",
"$$\n",
"\\det \\begin{pmatrix} a + a' & b + b' \\\\ c & d \\end{pmatrix} =\n",
"\\det \\begin{pmatrix} a & b \\\\ c & d \\end{pmatrix} +\n",
"\\det \\begin{pmatrix} a' & b' \\\\ c & d \\end{pmatrix} \\; .\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Or, in terms of our matrix $A$ from above, let's add $(1,2,3,4,5)$ to the first row:"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Matrix{Int64}:\n",
" 1 -2 -1 1 -1\n",
" 1 1 1 3 3\n",
" -1 2 -1 3 3\n",
" 2 -2 -1 2 1\n",
" -2 0 -2 -2 0"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Matrix{Int64}:\n",
" 1 2 3 4 5\n",
" 0 0 0 0 0\n",
" 0 0 0 0 0\n",
" 0 0 0 0 0\n",
" 0 0 0 0 0"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[1,0,0,0,0] * [1 2 3 4 5] # = column * row = outer product"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"54.0"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(A + [1,0,0,0,0] * [1 2 3 4 5])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This should be the same as $\\det A$ plus the determinant of $A$ with the first row replaced by $(1,2,3,4,5)$:"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Matrix{Int64}:\n",
" 1 2 3 4 5\n",
" 1 1 1 3 3\n",
" -1 2 -1 3 3\n",
" 2 -2 -1 2 1\n",
" -2 0 -2 -2 0"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A′ = copy(A)\n",
"A′[1,:] = [1,2,3,4,5] # replace first row\n",
"A′"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"54.0"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(A) + det(A′)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Yup, it matches (up to roundoff errors, of course)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Additional properties of determinants\n",
"\n",
"The following properties can be **derived from the above 3**, and are quite useful to know. Again, the numbering follows Strang, section 5.1:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. If two rows are equal, det = 0\n",
"\n",
"It's easy to see why this **follows from property 2**: if we swap two equal rows, the matrix doesn't change, but the determinant must flip sign. But this means:\n",
"\n",
"$$\\det A = -\\det A \\implies \\det A = 0$$\n",
"\n",
"For example:"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.0"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det([ 1 2 3 \n",
" 4 5 6\n",
" 1 2 3 ])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This property also makes sense if our expectation is that the determinant is zero for singular matrices: if two rows are equal, the matrix is singular."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 5. Subtracting a multiple of one row from another doesn’t change det\n",
"\n",
"Suppose we take a matrix $A$, and subtract (or add) a multiple of one row from another. For example:\n",
"\n",
"$$\n",
"\\det \\begin{pmatrix} a & b \\\\ c - \\alpha a & d - \\alpha b \\end{pmatrix} =\n",
"\\det \\begin{pmatrix} a & b \\\\ c & d \\end{pmatrix} -\n",
"\\alpha \\det \\begin{pmatrix} a & b \\\\ a & b \\end{pmatrix} =\n",
"\\det \\begin{pmatrix} a & b \\\\ c & d \\end{pmatrix} + 0\n",
"$$\n",
"\n",
"Here, we applied axiom 3 (linearity), and then property 4 (repeated rows).\n",
"\n",
"The same thing happens for *any* size of matrix.\n",
"\n",
"But this is *precisely* the kind of operation that we perform during Gaussian elimination. It has the crucial implications:\n",
"\n",
"* **Elimination operations** on rows **don't change the determinant**.\n",
"\n",
"* **Gaussian elimination without row swaps doesn't change the determinant**.\n",
"\n",
"And, by axiom 2:\n",
"\n",
"* **Gaussian elimination with row swaps** gives the **same determinant** but with **flipped sign for each row swap**.\n",
"\n",
"For example:"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Matrix{Float64}:\n",
" 1.0 -2.0 -1.0 1.0 -1.0\n",
" 0.0 3.0 2.0 2.0 4.0\n",
" 0.0 0.0 -2.0 4.0 2.0\n",
" 0.0 0.0 0.0 -2.0 2.22045e-16\n",
" 0.0 0.0 0.0 0.0 2.0"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"L, U = lu(A, NoPivot()) # elimination without row swaps\n",
"U"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(24.0, 23.999999999999993)"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(A), det(U)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 6. A matrix with a row of zeros has det = 0\n",
"\n",
"This is easy to see from axiom 3 (linearity): if we multiply the row of zeros by zero, it doesn't change the matrix but multiplies the determinant by zero, hence:\n",
"\n",
"$$\n",
"0 \\times \\det A = \\det A \\implies \\det A = 0\n",
"$$\n",
"\n",
"For example:"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.0"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det([1 2 3\n",
" 4 5 6\n",
" 0 0 0])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 7. If A is triangular then det(A) is the product of the diagonal entries\n",
"\n",
"This is another incredibly useful property. To see this, suppose we have an upper-triangular matrix $U$. Then:\n",
"\n",
"1. Eliminate \"upward\" above the pivots to get a diagonal matrix $D$. This doesn't change the determinant by property 5.\n",
"\n",
"2. Pull out each diagonal element by axiom 3 (linearity) until you get the identity matrix $I$ whose determinant is 1 by axiom 1:\n",
"$$\n",
"\\det \\begin{pmatrix} \\alpha_1 & & & \\\\ & \\alpha_2 & & \\\\ & & \\alpha_3 & \\\\ & & & \\ddots \\end{pmatrix} =\n",
"\\alpha_1 \\det \\begin{pmatrix} 1 & & & \\\\ & \\alpha_2 & & \\\\ & & \\alpha_3 & \\\\ & & & \\ddots \\end{pmatrix} = \\cdots = \\alpha_1 \\alpha_2 \\alpha_3 \\cdots \\det I = \\alpha_1 \\alpha_2 \\alpha_3 \\cdots\n",
"$$\n",
"which is precisely the product of the diagonals.\n",
"\n",
"If we have a zero diagonal entry, we can't eliminate upward above it (we can't divide by the diagonal \"pivot\"). But in that case we end up with a row of zeros after eliminating above the *other* diagonals, and by property 6 we get a zero determinant. So it still matches the product of the diagonal entries.\n",
"\n",
"Similarly for a lower triangular matrix, except that we eliminate \"downward\".\n",
"\n",
"We already saw an example of this earlier, but let's do it again. We got our $U$ matrix from elimination on $A$:"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Matrix{Float64}:\n",
" 1.0 -2.0 -1.0 1.0 -1.0\n",
" 0.0 3.0 2.0 2.0 4.0\n",
" 0.0 0.0 -2.0 4.0 2.0\n",
" 0.0 0.0 0.0 -2.0 2.22045e-16\n",
" 0.0 0.0 0.0 0.0 2.0"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"U"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Its diagonal entries are:"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5-element Vector{Float64}:\n",
" 1.0\n",
" 3.0\n",
" -2.0\n",
" -1.9999999999999998\n",
" 1.9999999999999996"
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"diag(U)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The product of these is:"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"23.999999999999993"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"prod(diag(U))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"which matches $\\det U$ (and $\\det A$):"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(23.999999999999993, 24.0)"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(U), det(A)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If we *do* need to compute the determinant, this gives us a very practical way to do it: **compute det(A) by taking the product of the pivots after elimination, with a sign flip for every row swap**, i.e.\n",
"\n",
"$$\n",
"\\boxed{\\det A = (-1)^\\mbox{# row swaps} \\times \\mbox{(product of pivots)} } \\, .\n",
"$$\n",
"\n",
"This is, in fact *exactly* what the Julia `det` function does, as you can check by looking at the source code:"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"det(A::AbstractMatrix{T}) where T in LinearAlgebra at /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/LinearAlgebra/src/generic.jl:1544"
],
"text/plain": [
"det(A::AbstractMatrix{T}) where T in LinearAlgebra at /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/LinearAlgebra/src/generic.jl:1544"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"@which det(A)"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"det(A::UpperTriangular) in LinearAlgebra at /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/LinearAlgebra/src/triangular.jl:2637"
],
"text/plain": [
"det(A::UpperTriangular) in LinearAlgebra at /Applications/Julia-1.8.app/Contents/Resources/julia/share/julia/stdlib/v1.8/LinearAlgebra/src/triangular.jl:2637"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"@which det(UpperTriangular(U))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"From the source code, this calls `det(lufact(A))`, which calls:"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"ename": "LoadError",
"evalue": "UndefVarError: lufact not defined",
"output_type": "error",
"traceback": [
"UndefVarError: lufact not defined",
"",
"Stacktrace:",
" [1] top-level scope",
" @ In[45]:1",
" [2] eval",
" @ ./boot.jl:368 [inlined]",
" [3] include_string(mapexpr::typeof(REPL.softscope), mod::Module, code::String, filename::String)",
" @ Base ./loading.jl:1428"
]
}
],
"source": [
"@which det(lufact(A))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 8. det(A) = 0 if and only if A is singular\n",
"\n",
"This follows from property 7. Since the determinant is ± the product of the pivots, we get zero if and only if there is a zero pivot, corresponding to a singular matrix."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 9. det(AB) = det(A) det(B)\n",
"\n",
"This is an amazing property of determinants, and probably the least obvious.\n",
"\n",
"A nice way to show this (from Strang's book) is simply to check that $$\\det(AB)/\\det(B)$$ **satisfies axioms 1,2,3 for A**. If it does, then it must be $\\det A$, and we are done! Let's check:\n",
"\n",
"1. Identity: If $A=I$, then $\\det(AB)/\\det(B) = \\det(B)/\\det(B) = 1$. ✓\n",
"2. Swaps: If we swap two rows of $A$, we also swap the *same* two rows of $AB$, hence $\\det(AB)/\\det(B)$ flips sign. ✓\n",
"3. Linearity:\n",
" - Scaling a row of $A$ by $\\alpha$ scales a row of $AB$ by $\\alpha$, which scales $\\det(AB)/\\det(B)$ by $\\alpha$. ✓\n",
" - Adding a row of $A$ to a row of $A'$ (with other rows the same) adds the same rows of $AB$ and $A'B$, so it adds $\\det(AB)/\\det(B)$ and $\\det(A'B)/\\det(B)$. ✓\n",
"\n",
"Let's try it:"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Matrix{Int64}:\n",
" 3 2 -2 -2 3\n",
" -3 3 2 -1 -3\n",
" -1 0 -3 -1 -3\n",
" -2 2 1 1 3\n",
" 0 3 0 1 1"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"B = rand(-3:3, 5,5)"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(24.0, 700.0)"
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(A), det(B)"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(16799.999999999996, 16800.0)"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(A*B), det(A)*det(B)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Matrix inverses\n",
"\n",
"This rule has important consequences for matrix inverses. First:\n",
"\n",
"$$\\det (A^{-1}) = 1 / \\det(A)$$\n",
"\n",
"Proof: $1 = \\det(I) = \\det(A A^{-1}) = \\det(A) \\det(A^{-1})$.\n",
"\n",
"For example:"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(0.04166666666666666, 0.041666666666666664)"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(inv(A)), 1/det(A)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Recall from last lecture that $X A X^{-1}$ corresponds simply to a **change of basis** from $A$. (We will later call this a **similar matrix** to $A$). Now we know:\n",
"\n",
"$$\n",
"\\det(X A X^{-1}) = \\det(X) \\det(A) \\det(X^{-1}) = \\det(A) \\; .\n",
"$$\n",
"\n",
"That is, a **change of basis doesn't change the determinant**."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 10. det(Aᵀ) = det(A)\n",
"\n",
"This is another non-obvious, but very important, property of determinants. It is relatively easy to see from properties 7 and 9, however.\n",
"\n",
"In particular, factorize $PA = LU$, or $A = P^T L U \\implies A^T = U^T L^T P$. Then, from property 9:\n",
"\n",
"$$\n",
"\\det(A^T) = \\det(U^T) \\det(L) \\det(P) = \\det(U^T) \\det(P) = \\det(P) \\times \\mbox{(product of pivots)} \\; ,\n",
"$$\n",
"\n",
"where we have used the fact that $\\det L^T = 1$ since $L^T$ is *upper* triangular and the diagonal entries of $L^T$ are all 1's, while $\\det U^T$ is the determinant of a *lower* triangular matrix with the pivots on the diagonal.\n",
"\n",
"But we also have that the permutation $P$ is formed by taking the identity matrix $I$ and swapping rows (for each rows wap during elimination), so\n",
"\n",
"$$\n",
"\\det P = (-1)^\\mbox{# row swaps}\n",
"$$\n",
"\n",
"So:\n",
"\n",
"$$\n",
"\\det(A^T) = (-1)^\\mbox{# row swaps} \\times \\mbox{(product of pivots)}\n",
"$$\n",
"\n",
"which is exactly the same as $\\det A$ from earlier."
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(24.0, 23.99999999999999)"
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"det(A), det(A')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"# Useful applications of determinants\n",
"\n",
"Ignoring formulas (e.g. Cramer's rule, a formula for $A^{-1}$ — see Strang, section 5.3) that are mainly useful for tiny matrices, here are some examples of real usages of determinants **even for large matrices**:\n",
"\n",
"* Understanding **eigenvalues**: determinants will turn eigenvalues into polynomial roots, and since we know about polynomial roots, that tells us a lot about eigenvalues. (This is *not* how eigenvalues are *computed* in practice, however!)\n",
"\n",
" - There is also something called a [nonlinear eigenproblem](https://en.wikipedia.org/wiki/Nonlinear_eigenproblem), arising in many science and engineering problems, in which the determinant plays a basic conceptual role. Again, however, computational methods typically avoid computing determinants explicitly except for tiny matrices.\n",
"\n",
"* Proofs: Determinants show up in a lot of proofs in matrix theory, because they reduce matrices to numbers that have nice properties and are easy to reason about. One also often sees things like the [adjugate matrix](https://en.wikipedia.org/wiki/Adjugate_matrix) and the [Cayley–Hamilton theorem](https://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theorem), both related to determinants.\n",
"\n",
" - That is, we often use determinants to help use understand and derive things in linear algebra, even if the final result doesn't require us to *compute* the determinant for any practical purpose.\n",
"\n",
"* [Jacobian factors](https://en.wikipedia.org/wiki/Jacobian_matrix_and_determinant): in multivariable calculus, a factor of $|\\det J|$ arises when you perform a *change of variables* in integration, where $J$ is a Jacobian matrix.\n",
"\n",
" - The reason a determinant arises here is that, more generally, **det(A) is the volume of a parallelepiped** (\"box\") whose edges are given by the columns of $A$.\n",
" \n",
" - Integration may sound like something that only happens in a few dimensions (= tiny matrices J), but extremely high dimensional (even infinite-dimensional) integrals appear in statistics, quantum field theory, bioinformatics, and other fields.\n",
"\n",
"* High-dimensional [Gaussian integrals](https://en.wikipedia.org/wiki/Gaussian_integral) often arise in **statistics** and related areas of science (e.g. [quantum field theory](https://en.wikipedia.org/wiki/Common_integrals_in_quantum_field_theory)), and the inverse of the square root of a determinant appears in the answer. Often, one wants the logarithm of the result, in which case what arises is the **log determinant** $\\log \\det A$, an important matrix function.\n",
"\n",
"This is no doubt an incomplete list. Nevertheless, although determinants are a much more marginal topic in modern linear algebra than they were in the 19th century, they have hardly disappeared."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# A “Simple” But Horrible Formula\n",
"\n",
"You probably learned a neat formula for the determinant of a $2\\times2$ matrix at some point:\n",
"\n",
"$$\n",
"\\det \\begin{pmatrix} a & b \\\\ c & d \\end{pmatrix} = ad - bc \\;\n",
"$$\n",
"\n",
"You might have even learned a formula for $3\\times3$ matrices. You might be hoping, therefore, that there would be an extension of this \"nice\" formula (which seems a lot easier than doing elimination to get pivots) to arbitrary matrices. There is!\n",
"\n",
"Here it is (see Strang, section 5.2):\n",
"\n",
"$$\n",
"\\det A = \\sum_{\\mbox{permutations }p} \\operatorname{sign}(p) \\times (\\mbox{product of diagonals of }A\\mbox{ with columns permuted by }p)\n",
"$$\n",
"\n",
"The important thing to know is that you have to consider **all permutations (re-orderings)** of $(1,2,3,\\ldots,n)$. (The [sign of the permutation](https://en.wikipedia.org/wiki/Parity_of_a_permutation) corresponds to the number of swaps it involves.) There are $n! = n (n-1)(n-2)\\cdots 1$ (*n factorial*) re-orderings.\n",
"\n",
"That means that this formula requires $\\sim n \\times n!$ scalar operations, which is **worse than exponential** in $n$. This is **far more expensive than elimination** ($\\sim n^3$), making this formula **computationally useless** for $n > 3$.\n",
"\n",
"(There is also *another* computationally useless formula involving [minors and cofactors](https://en.wikipedia.org/wiki/Minor_(linear_algebra)); see Strang, section 5.2.)\n",
"\n",
"The permutation formula is still sometimes useful *conceptually*, however."
]
}
],
"metadata": {
"@webio": {
"lastCommId": null,
"lastKernelId": null
},
"anaconda-cloud": {},
"kernelspec": {
"display_name": "Julia 1.8.0",
"language": "julia",
"name": "julia-1.8"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "1.8.1"
}
},
"nbformat": 4,
"nbformat_minor": 1
}