Linear Algebra

The equation $x^2 + 1 = 0$ has no solutions in real numbers. This is inconvenient—since many problems in physics and mathematics lead precisely to such equations. Mathematicians of the 16th century (Cardano, Bombelli) began to “pretend” that $\sqrt{-1}$ exists, and discovered that it works.

The imaginary unit $i$ is defined by the condition $i^2 = -1$. A complex number $z = a + bi$, where $a = \operatorname{Re}(z)$ is the real part, $b = \operatorname{Im}(z)$ is the imaginary part.

Division: $\frac{a+bi}{c+di} = \frac{(a+bi)(c-di)}{|c+di|^2} = \frac{(ac+bd) + (bc-ad)i}{c^2+d^2}$.

Conjugate: $\bar{z} = a - bi$. Properties: $z \cdot \bar{z} = a^2 + b^2 = |z|^2$ (a real number).

Formulas

A matrix is a rectangular array of numbers. Notation: $A = (a_{ij})$, $i = 1,\ldots,m$ (rows), $j = 1,\ldots,n$ (columns). $A$ is a matrix of size $m \times n$.

Matrices arose as a convenient way to record systems of linear equations. Today they are the primary object of linear algebra and computational mathematics.

Matrix multiplication: $C = AB$, where $c_{ij} = \sum_k a_{ik} \cdot b_{kj}$. Requirement: $A$ of size $m \times k$, $B$ of size $k \times n$. Result $C$ of size $m \times n$.

Multiplication is not commutative: $AB \ne BA$ in general! This is a fundamental difference between matrices and numbers.

Formulas

A determinant is a scalar associated with a square matrix. The intuition: det A is the “volume” of the parallelepiped formed by the rows (or columns) of the matrix. If det A = 0, the columns are linearly dependent—the “parallelepiped” is degenerate (flat).

Geometrically: |ad−bc| is the area of the parallelogram with sides (a,b) and (c,d).

The determinant is the unique function of the rows of a matrix possessing three properties: 1. Multilinearity in the rows 2. Skew-symmetry (swapping two rows changes the sign) 3. det E = 1

det A = Σⱼ aᵢⱼ Aᵢⱼ, where Aᵢⱼ = (−1)^(i+j) Mᵢⱼ is the cofactor, and Mᵢⱼ is the minor (the determinant of the submatrix without the i-th row and j-th column).

Nineteenth-century algebra made a central discovery: different mathematical objects (numbers, permutations, symmetries of polyhedra, matrices) obey the same abstract laws. By studying these laws in general form, we obtain results at once for all concrete cases.

Galois and Cauchy in the first half of the 19th century laid the foundations of group theory by studying symmetries of equations.

A group is a set $G$ with a binary operation $\ast$ satisfying: 1. Closure: $a \ast b \in G$ for all $a, b \in G$ 2. Associativity: $(a \ast b) \ast c = a \ast (b \ast c)$ 3. Identity element: there exists $e$ such that $a \ast e = e \ast a = a$ 4. Inverse element: for each $a$ there exists $a^{-...

($\mathbb{R}^*,\cdot$) $=$ ($\mathbb{R}\setminus\{0\},\cdot$) — nonzero real numbers under multiplication.

The integers ℤ have two operations: addition and multiplication. The generalization is a ring.

A ring (R, +, ·): (R, +) is an abelian group, multiplication is associative, distributivity holds: $a(b+c) = ab+ac$ and $(a+b)c = ac+bc$.

An ideal $I \subseteq R$ is a subgroup under addition, closed under multiplication by ring elements: $r \cdot I \subseteq I$ and $I \cdot r \subseteq I$.

The quotient ring $R/I$: elements are cosets $a + I$. This is a ring with operations $(a+I) + (b+I) = (a+b)+I$, $(a+I)(b+I) = ab+I$.

The system Ax = b (m equations, n unknowns) is the central problem of computational and theoretical mathematics. When is the system consistent? How many solutions does it have? How can they be found?

We reduce the augmented matrix [A|b] to row-echelon form using elementary row operations. Row-echelon form: in each nonzero row, the leading entry stands further to the right than in the previous row.

Reduced row-echelon form (Gauss–Jordan): the leading entry in each row equals 1, and in its column there are zeros above and below.

The system Ax = b is consistent (has at least one solution) if and only if rank(A) = rank(A|b).

Arrows in space can be added and multiplied by numbers. These operations obey certain laws. Abstracting these laws yields the concept of a vector space.

A vector space over a field F is a set V with addition (V×V→V) and scalar multiplication (F×V→V) operations that satisfy 8 axioms (associativity, commutativity of addition, neutral element, inverse, distributivity, etc.).

The space of polynomials of degree ≤ n: Pₙ. Dim = n+1. Basis: {1, x, x², ..., xⁿ}.

Vectors v₁, ..., vₖ are linearly dependent if there exist not all zero α₁, ..., αₖ such that α₁v₁ + ... + αₖvₖ = 0.

Formulas

A mapping $f: V \to W$ between vector spaces is called linear (a homomorphism) if:

This is the “dimension conservation law”: what is “lost” ($\ker f$) plus what is “achieved” ($\mathrm{Im}\, f$) equals the original.

Fix bases $B$ in $V$ and $C$ in $W$. The matrix $A$ of a linear transformation $f$ is the matrix whose columns are the coordinates of $f(b_1), \ldots, f(b_n)$ in the basis $C$.

Every linear transformation between finite-dimensional spaces is specified by a matrix (with fixed bases), and vice versa.

Formulas

What happens to most vectors when multiplied by a matrix? They change both their length and direction. But some vectors change only their length — remaining on the same line. These special vectors are fundamental.

An eigenvector of a matrix A is a nonzero vector v such that Av = λv, where λ is an eigenvalue.

Physically: an eigenvector is an "invariant direction" of the transformation. Scaling without rotation.

Characteristic polynomial: $p_A(\lambda) = \det(A - \lambda E)$ — a degree n polynomial in λ.

Not every operator is diagonalizable. The matrix [[1,1],[0,1]] has a unique eigenvalue 1 of multiplicity 2, but only one eigenline—the space of eigenvectors is one-dimensional. Diagonalization is impossible.

What can be done in this case? Reduce to an almost diagonal form—the Jordan canonical form.

A Jordan block J(λ, k) is a k×k matrix of the following type: λ on the diagonal, 1 above the diagonal, 0 everywhere else.

J(λ, 1) = (λ) — a scalar. J(λ, 2) = [[λ,1],[0,λ]]. J(λ, 3) = [[λ,1,0],[0,λ,1],[0,0,λ]].

A real matrix may have complex eigenvalues, which occur in pairs: $\lambda = \alpha \pm \beta i$. In the real canonical form, instead of complex cells, there appear real $2 \times 2$ blocks $\begin{bmatrix} \alpha & -\beta \\ \beta & \alpha \end{bmatrix}$ (rotation-stretch matrix).

Example: the rotation matrix $\begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}$ — two complex conjugate eigenvalues $e^{\pm i\theta}$.

Over an arbitrary field (not necessarily algebraically closed), the Jordan form may not exist. The rational canonical form exists over any field.

For the polynomial $p(t) = t^n + a_{n-1} t^{n-1} + \ldots + a_1 t + a_0$ the companion matrix is:

A quadratic form is a homogeneous polynomial of degree 2: $Q(x) = \sum_{ij} a_{ij} x_i x_j = x^T A x$, where $A$ is a symmetric matrix ($A = A^T$).

Examples: $Q(x, y) = x^2 + 2 x y + 3 y^2$ corresponds to $A = \begin{bmatrix} 1 & 1 \\ 1 & 3 \end{bmatrix}$.

Sylvester's Law of Inertia: Any quadratic form over $\mathbb{R}$ can be reduced by a change of variables to the form $x_1^2 + \ldots + x_p^2 - x_{p+1}^2 - \ldots - x_{p+i}^2$ ($p$ positive, $i$ negative, the rest zero). The numbers $p$ and $i$ do not depend on the choice of substitution.

Positive definite: $Q(x) > 0$ for all $x \ne 0$ $\iff$ all eigenvalues of $A$ are

Let us add to a vector space the notions of length and angle — the scalar product.

Euclidean space is a real vector space $V$ with a scalar product $(\cdot, \cdot): V \times V \to \mathbb{R}$ satisfying:

Norm: $\|v\| = \sqrt{(v, v)}$. Angle: $\cos \theta = \frac{(u, v)}{\|u\| \cdot \|v\|}$.

Orthonormal basis: $(e_i, e_j) = \delta_{ij}$ (Kronecker delta). In an orthonormal basis: $(u, v) = \sum_i u_i v_i$ (the standard scalar product in $\mathbb{R}^n$).

Formulas

For a linear operator $A$ on a Euclidean space: the adjoint operator $A^*$ satisfies $(Av, w) = (v, A^*w)$ for all $v, w$.

In matrix form (orthonormal basis): $A^* = A^\mathsf{T}$ (the transposed matrix).

Spectral theorem: A symmetric operator in a finite-dimensional Euclidean space has real eigenvalues and an orthonormal basis of eigenvectors (it can be diagonalized by an orthogonal transformation).

Proof: the eigenvalues are real (from $(Av, v) = \lambda(v, v) = (v, Av) = \bar{\lambda}(v, v)$); eigenvectors of different values are orthogonal.

Formulas

For a normal operator $A$ ($AA^* = A^*A$) on a finite-dimensional unitary space: there exists an orthonormal basis of eigenvectors. Normal operators include Hermitian, skew-Hermitian, and unitary operators.

This is a unified "framework" result for the most important classes of operators.

If $A = QDQ^{-1}$ ($Q$ is orthogonal/unitary), then $f(A) = Q f(D) Q^{-1} = Q \operatorname{diag}(f(\lambda_1),...,f(\lambda_n)) Q^{-1}$.

This is an elegant way to compute: matrix roots ($f(t) = \sqrt{t}$), exponentials ($f(t) = e^t$), logarithms, and other functions.

Definitions

Multilinear form

— a function $f: V_1 \times \ldots \times V_k \to F$, linear in each argument. A tensor of type $(p, q)$ has $p$ contravariant and $q$ covariant indices.

A tensor is a multidimensional array of numbers that transforms in a “proper way” under a change of basis. Scalars are tensors of rank 0, vectors are tensors of rank 1, matrices are tensors of rank 2.

Multilinear form — a function $f: V_1 \times \ldots \times V_k \to F$, linear in each argument. A tensor of type $(p, q)$ has $p$ contravariant and $q$ covariant indices.

If $V$ and $W$ are vector spaces, their tensor product $V \otimes W$ is a new vector space of dimension $\dim V \cdot \dim W$.

If $\{e_i\}$ is a basis of $V$ and $\{f_j\}$ is a basis of $W$, then $\{e_i \otimes f_j\}$ is a basis of $V \otimes W$.

Exterior algebra $\Lambda V$ is an algebra with anticommutative multiplication: $v \wedge w = -w \wedge v$, and in particular $v \wedge v = 0$.

Basis of $\Lambda^2(\mathbb{R}^n)$: $\{e_i \wedge e_j : i < j\}$. Basis of $\Lambda^n(\mathbb{R}^n)$: one-dimensional.

The determinant is the unique (up to scalar multiplication) $n$-form on an $n$-dimensional space:

$ \det A = \frac{e_1 \wedge \ldots \wedge e_n(Ae_1, \ldots, Ae_n)}{(e_1 \wedge \ldots \wedge e_n)(e_1, \ldots, e_n)}. $

A representation of a group G is a homomorphism $\rho: G \to GL(V)$, that is, each element of the group is assigned an invertible linear operator on $V$ such that $\rho(gh) = \rho(g)\rho(h)$.

The dimension of the representation = $\dim V$. Matrix coefficients: $\rho_{ij}(g)$ are numbers.

A subspace $U \subseteq V$ is invariant if $\rho(g)U \subseteq U$ for all $g \in G$. A representation is irreducible if there are no nontrivial invariant subspaces.

Maschke's Theorem: Any finite-dimensional representation of a finite group over a field of characteristic 0 (or not dividing $|G|$) is completely reducible: it decomposes into a direct sum of irreducible ones.

A subgroup N is called normal (N ⊲ G) if gN = Ng for all g ∈ G, that is, gNg⁻¹ = N.

Examples: {e} and G are always normal. In an abelian group — any subgroup is normal. The center Z(G) = {g: gx = xg ∀x} is normal.

A group is simple if the only normal subgroups are {e} and G itself. Simple groups are the “atoms” of group theory.

The alternating group Aₙ (even permutations) is simple for n ≥ 5. This is a key fact in the proof of the unsolvability of the general equation of degree ≥ 5 in radicals (Abel–Ruffini theorem).

If $|G| = p^m \cdot k$, where $p$ is prime and $p \nmid k$, then a subgroup of order $p^m$ is called a Sylow p-subgroup.

1. Existence: In a finite group $G$ there exists a Sylow $p$-subgroup for every prime $p$.

2. Conjugacy: All Sylow $p$-subgroups are conjugate: if $P$ and $P'$ are Sylow $p$-subgroups, then $P' = gPg^{-1}$ for some $g$.

3. Number: The number $n_p$ of Sylow $p$-subgroups satisfies: $n_p \equiv 1 \pmod{p}$ and $n_p \mid |G|/p^m$.

Évariste Galois in 1830 established a deep connection between field extensions and groups. To each extension $K/F$, one associates the Galois group $\mathrm{Gal}(K/F)$ — the group of automorphisms of the field $K$ that fix $F$.

$\mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}$ — a chain of extensions. $[\mathbb{C}:\mathbb{R}] = 2$, $[\mathbb{R}:\mathbb{Q}] = \infty$.

$\mathbb{Q}(\sqrt{2}) = \{a + b\sqrt{2}: a, b \in \mathbb{Q}\}$ — an extension of degree $2$. The minimal polynomial of $\sqrt{2}$ over $\mathbb{Q}$: $x^2 - 2$.

$\mathrm{Gal}(K/F) = \{\sigma: K \to K \mid \sigma \text{ is an automorphism},\ \sigma|_F = \mathrm{id}\}$.

A vector space is a module over a field. If we replace the field with a ring, we obtain a module—a more general structure in which “scalar multiplication” might not possess inverses.

Left R-module M: an abelian group (M, +) with an operation r·m (r ∈ R, m ∈ M), satisfying the axioms of distributivity and associativity.

Examples: ℤ-modules are simply abelian groups; K-modules = K-vector spaces; ideals of a ring R are R-modules.

A free module: has a basis (like a vector space). $R^n = R \times ... \times R$.

A chain complex is a sequence of abelian groups (or modules) and homomorphisms: ... → Cₙ₊₁ → Cₙ → Cₙ₋₁ → ... with the condition dᵢdᵢ₊₁ = 0 (d² = 0).

Singular homology of a topological space X: we construct a chain complex from singular simplices (continuous images of standard simplices) with a boundary operator.

H₀(X) ≅ ℤ^(number of connected components). H₁(X) — “holes” of dimension 1 (cycles). H₂(X) — “voids”, etc.

H*(X × Y) is computed in terms of H*(X) and H*(Y) according to the Künneth formula: H_n(X×Y) ≅ ⊕_{p+q=n} H_p(X) ⊗ H_q(Y) ⊕ ⊕_{p+q=n-1} Tor(H_p(X), H_q(Y)).

A ring $R$ is Noetherian (in terms of the ascending chain condition on ideals) if every ascending chain of ideals $I_1 \subseteq I_2 \subseteq \ldots$ stabilizes.

Emmy Noether in the 1920s established that this condition is the correct generalization of finiteness for rings.

Examples: fields, $\mathbb{Z}$, $K[x_1, \ldots, x_n]$ (Hilbert's basis theorem).

Hilbert's Basis Theorem: If $R$ is Noetherian, then $R[x]$ is Noetherian. Consequently, $K[x_1, \ldots, x_n]$ is Noetherian — every ideal is finitely generated.