Linear-2 1

Determinant

\begin{matrix} Determinant is a way to calculate area (volume in 3D, etc.) of a figure \\ defined by n vectors v_{1}, v_{2}, v_{3}, \dots, v_{n} \end{matrix}

Permutation #definition

\begin{matrix} Permutation σ : [n] \to [n] is a bijective function \\ is a set of values {σ (1), σ (2), \dots, σ (n)} \\ For example: \\ (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 2 & 4 \end{matrix}) \\ Which can in turn be expressed as (2, 5, 4) (3, 1) \\ (1, 3, 2) \neq (1, 2, 3) = (2, 3, 1) \end{matrix}

Transposition #definition

\begin{matrix} Let i, j \in [n] \\ (i, j) is called transposition if i < j and σ (i) > σ (j) \end{matrix}

\begin{matrix} (1, 2, 3) ⟹ {\begin{matrix} σ (1) = 2 \\ σ (2) = 3 \\ σ (3) = 1 \end{matrix} ⟹ {\begin{matrix} 1 < 2, σ (1) < σ (2) \\ 2 < 3, σ (2) > σ (3) \\ 1 < 3, σ (1) > σ (3) \end{matrix} \end{matrix}

Permutation sign #definition

\begin{matrix} Let k be the number of transpositions in σ \\ Permutation sign is then calculated and denoted as s g n (σ) = (- 1)^{k} \end{matrix}

Symmetric group #definition

\begin{matrix} Set of all possible permutations of [n] is denoted as \\ S_{n} = {{σ (1), σ (2), \dots, σ (n)} | σ : [n] \to [n] is bijective} \end{matrix}

\begin{matrix} S_{2} = {(\begin{matrix} 1 & 2 \\ 1 & 2 \end{matrix}), (\begin{matrix} 1 & 2 \\ 2 & 1 \end{matrix})} = {\begin{matrix} (1) (2) \\ (1, 2) \end{matrix} \\ S_{3} = {(\begin{matrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{matrix})} = \\ = {\begin{matrix} (1) (2) (3) \to s g n (σ) = (- 1)^{0} \\ (1) (2, 3) \to s g n (σ) = (- 1)^{1} \\ (1, 2) (3) \to s g n (σ) = (- 1)^{1} \\ (1, 2, 3) \to s g n (σ) = (- 1)^{2} \\ (1, 3, 2) \to s g n (σ) = (- 1)^{2} \\ (1, 3) (2) \to s g n (σ) = (- 1)^{3} \end{matrix} \end{matrix}

Determinant #definition

\begin{matrix} Let | | : F^{n \times n} \to F \\ \forall A \in F^{n \times n} : | A | = \sum_{σ \in S_{n}} a_{1 σ (1)} \cdot a_{2 σ (2)} \cdot \dots \cdot a_{n σ (n)} \\ Sometimes denoted as det (A) \end{matrix}

\begin{matrix} A = (\begin{matrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix}) ⟹ det (A) = | A | = \underset{σ (1) = 1, σ (2) = 2, s g n (σ) = 1}{\underset{⏟}{a_{11} a_{22}}} - \underset{σ (1) = 2, σ (2) = 1, s g n (σ) = - 1}{\underset{⏟}{a_{12} a_{21}}} \\ A = (\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix}) ⟹ det (A) = | A | = \\ = a_{11} a_{22} a_{33} - a_{11} a_{23} a_{32} - a_{12} a_{21} a_{33} + a_{12} a_{23} a_{31} + a_{13} a_{21} a_{32} - a_{13} a_{22} a_{31} = \\ = 45 - 48 - 72 + 84 + 96 - 105 = 0 \end{matrix}

Determinant of triangular matrix #lemma

\begin{matrix} Let A \in F^{n \times n} be a triangular matrix \\ Then | A | = \prod_{i = 1}^{n} a_{i i} \\ Proof: \\ Let σ \neq I \\ ⟹ \exists k \geq 2 : (x_{1}, \dots, x_{k}) \in σ \\ Case 1. Let \exists j \in [k - 1] : x_{j} > x_{j + 1} \\ ⟹ x_{j} > σ (x_{j}) ⟹ a_{x_{j} σ (x_{j})} = 0 ⟹ s g n (σ) a_{1 σ (1)} \dots a_{n σ (n)} = 0 \\ Let x_{1} < x_{2} < \dots < x_{k} \\ ⟹ x_{k} > x_{1} = σ (x_{k}) ⟹ a_{x_{k} σ (x_{k})} = 0 ⟹ s g n (σ) a_{1 σ (1)} \dots a_{n σ (n)} = 0 \\ ⟹ | A | = \prod_{i = 1}^{n} a_{i i} \\ Similar proof for lower-triangular matrix \end{matrix}

Row-linearity of determinant #lemma

\begin{matrix} Let A \in F^{n \times n} \\ Let i \in [n] \\ Let \exists v, u \in F^{n} : R_{i} (A) = v + α u \\ Let A_{v} = {\begin{matrix} R_{j} (A_{v}) = R_{j} (A) & j \neq i \\ R_{j} (A_{v}) = v & j = i \end{matrix} \\ Let A_{u} = {\begin{matrix} R_{j} (A_{v}) = R_{j} (A) & j \neq i \\ R_{j} (A_{v}) = u & j = i \end{matrix} \\ Then | A | = | A_{v} | + α | A_{u} | \end{matrix}

Determinant of a matrix with two equal rows #lemma

\begin{matrix} Let A \in F^{n \times n} \\ Let \exists i \neq j \in [n] : R_{i} (A) = R_{j} (A) \\ Then | A | = 0 \end{matrix}

Determinant of a matrix with a zero row #lemma

\begin{matrix} Let \exists i \in [n] : R_{i} (A) = 0 \\ Then | A | = 0 \\ Proof: \\ \forall σ : a_{i σ (i)} = 0 ⟹ \forall σ : s g n (σ) a_{1 σ (1)} \dots a_{n σ (n)} = 0 \\ ⟹ | A | = 0 \end{matrix}

Determinant after elementary row-operations #lemma

\begin{matrix} Let A \in F^{n \times n} \\ Let B = p (A) \\ Then {\begin{matrix} p : α R_{i} ⟹ | B | = α | A | \\ p : R_{i} \leftrightarrow R_{j} ⟹ | B | = - | A | \\ p : R_{i} + α R_{j} ⟹ | B | = | A | \end{matrix} \\ Proof: \\ Let A = (\begin{matrix} v_{1} \\ v_{2} \\ ⋮ \\ v_{n} \end{matrix}) \\ Let p : α R_{i} \\ ⟹ B = (\begin{matrix} v_{1} \\ ⋮ \\ α v_{i} \\ ⋮ \\ v_{n} \end{matrix}) ⟹ R_{i} (B) = 0 + α v_{i} ⟹ | B | = | B_{0} | + α | B_{v_{i}} | = 0 + α | A | = α | A | \\ Let p : R_{i} \leftrightarrow R_{j} \\ Let i > j (WLOG) \\ Let X = (\begin{matrix} v_{1} \\ ⋮ \\ v_{i} + v_{j} \\ ⋮ \\ v_{i} + v_{j} \\ ⋮ \\ v_{n} \end{matrix}) ⟹ 0 = | X | = | \begin{matrix} v_{1} \\ ⋮ \\ v_{i} \\ ⋮ \\ v_{i} + v_{j} \\ ⋮ \\ v_{n} \end{matrix} | + | \begin{matrix} v_{1} \\ ⋮ \\ v_{j} \\ ⋮ \\ v_{i} + v_{j} \\ ⋮ \\ v_{n} \end{matrix} | = \\ = | \begin{matrix} - v_{1} - \\ ⋮ \\ - v_{i} - \\ ⋮ \\ - v_{i} - \\ ⋮ \\ - v_{n} - \end{matrix} | + | \begin{matrix} - v_{1} - \\ ⋮ \\ - v_{i} - \\ ⋮ \\ - v_{j} - \\ ⋮ \\ - v_{n} - \end{matrix} | + | \begin{matrix} - v_{1} - \\ ⋮ \\ - v_{j} - \\ ⋮ \\ - v_{i} - \\ ⋮ \\ - v_{n} - \end{matrix} | + | \begin{matrix} - v_{1} - \\ ⋮ \\ - v_{j} - \\ ⋮ \\ - v_{j} - \\ ⋮ \\ - v_{n} - \end{matrix} | = 0 + | A | + | B | + 0 \\ ⟹ | A | + | B | = 0 ⟹ | B | = - | A | \\ Let p : R_{i} + α R_{j} \\ ⟹ B = (\begin{matrix} v_{1} \\ ⋮ \\ v_{i} + α v_{j} \\ ⋮ \\ v_{n} \end{matrix}) ⟹ | B | = | A | + α | \begin{matrix} - v_{1} - \\ ⋮ \\ - v_{j} - \\ ⋮ \\ - v_{j} - \\ ⋮ \\ - v_{n} - \end{matrix} | = | A | \end{matrix}

Properties of elementary row-operations determinant #lemma

\begin{matrix} Let A \in F^{n \times n} \\ p : α R_{i} ⟹ | p (I) | = α | I | = α \\ p : R_{i} \leftrightarrow R_{j} ⟹ | p (I) | = - | I | = - 1 \\ p : R_{i} + α R_{j} ⟹ | p (I) | = | I | = 1 \\ ⟹ | p (I) A | = | p (I) | \cdot | A | \\ ⟹ (Simple proof by induction) | (\prod_{i = 1}^{k} p_{i} (I)) A | = (\prod_{i = 1}^{k} | p_{i} (I) |) | A | \\ ⟹ \forall A, B \in F^{n \times n} : A = (\prod_{i = 1}^{k} p_{i}) B ⟹ \exists α \neq 0 \in F : | A | = α | B | \end{matrix}

Invertibility of matrix and determinant #theorem

\begin{matrix} Let A \in F^{n \times n} \\ Then | A | \neq 0 ⟺ A is invertible \\ Proof: \\ Let A be non-invertible \\ ⟹ \exists i \in [n] : R_{i} (C F (A)) = 0 ⟹ | C F (A) | = 0 = α | A | \underset{α \neq 0}{\underset{⏟}{⟹}} | A | = 0 \\ Let | A | = 0 \\ ⟹ | A | = α | C F (A) | = 0 \\ α \neq 0 ⟹ | C F (A) | = 0 \\ | I | \neq 0 ⟹ C F (A) \neq I ⟹ A is not invertible \end{matrix}

Determinant of two matrix product #lemma

\begin{matrix} Let A, B \in F^{n \times n} \\ Then | A B | = | A | \cdot | B | \\ Proof: \\ Let A be non-invertible \\ ⟹ | A | = 0 ⟹ | A | \cdot | B | = 0 \\ r a n k (A) < n ⟹ r a n k (A B) \leq r a n k (A) < n ⟹ A B is non-invertible \\ ⟹ | A B | = 0 = | A | \cdot | B | \\ Let A be invertible \\ ⟹ A = (\prod_{i = 1}^{k} p_{i} (I)) C F (A) = \prod_{i = 1}^{k} p_{i} (I) ⟹ | A | = | \prod_{i = 1}^{k} p_{i} (I) | = \prod_{i = 1}^{k} | p_{i} (I) | \\ ⟹ A B = (\prod_{i = 1}^{k} p_{i} (I)) B \\ ⟹ | A B | = | (\prod_{i = 1}^{k} p_{i} (I)) B | = (\prod_{i = 1}^{k} | p_{i} (I) |) | B | = | A | \cdot | B | \end{matrix}