Matrices and algebraic structures: synthesis and challenges

Summary

This lesson closes the unit on matrices and algebraic structures. It gathers into a deductive chain what was achieved in its seven lessons: the matrix product, born of the composition of linear substitutions; the complete solution of linear systems by the Gauss-Jordan method and the Rouché-Capelli theorem (known in the Spanish-speaking world as the Rouché-Frobenius theorem); the determinant as a signed area and as a criterion of uniqueness; the inverse matrix and the conditions equivalent to invertibility; the reading of matrices as transformations of the plane; the copy of the complex numbers inside the matrices; and the notions of group, algebraic ring, field and isomorphism, which give a name to what all those computations have in common. It explains how the unit takes up results of the earlier units and of the course Algebra and Geometry I, what was admitted without proof and how it prepares the following unit, on the analytic geometry of space, and the Calculus I course. It ends with ten challenges, harder than the problems of the lessons, that combine several of them.

Learning objectives

Reconstruct the chain of definitions and theorems of the unit, from the matrix product to isomorphisms, explaining which result builds on which.
Relate the results of the unit to those of the earlier units and of Course I, in particular to linear systems, vectors, rotation of axes, the polar form and the arithmetic of remainders, distinguish what was proved from what was admitted, and anticipate their use in the geometry of space.
Solve problems that combine determinants, inverses, transformations, matrices of complex numbers and algebraic structures, choosing in each case the appropriate tool.
Carry a problem over from one structure to another by means of a correspondence that preserves the operations, and use the invariants of an isomorphism to decide whether two groups are the same.

What the unit achieved

The algebra of matrices and linear systems

The starting point was an observation about linear substitutions. In the lesson on matrices and matrix operations, the array of the composite substitution was obtained by multiplying the arrays of the two substitutions row by column, and that rule was taken as the definition of the product. From it followed associativity, by interchanging the order of two sums, distributivity and the neutrality of the identity matrix; and, in the opposite direction, it was seen that the product is not commutative, that it admits zero divisors and that there are nonzero matrices with some power equal to zero. The transpose reverses the order of the factors, $(AB)^{\mathsf{T}} = B^{\mathsf{T}} A^{\mathsf{T}}$ , and the trace does not distinguish the order, $\operatorname{tr}(AB) = \operatorname{tr}(BA)$ , whence the equation $AB - BA = I$ has no solution in any order.

With the product, every linear system was written as a single equation $AX = B$ . The lesson on linear systems and the Gauss-Jordan method proved that elementary row operations preserve the solutions and that every matrix reduces to a reduced row echelon form; it proved, by induction on the number of columns, that this form is unique, whence the rank does not depend on the path of the elimination, and it proved the Rouché-Capelli theorem: the system is consistent if and only if $\operatorname{rank}(A) = \operatorname{rank}(M)$ , and in that case its solutions depend on $n - r$ free parameters. It followed that a linear system never has exactly two solutions, and that a homogeneous system with fewer equations than unknowns has nontrivial solutions.

The determinant and the inverse

Now, for square systems one wishes to decide uniqueness without going through the whole elimination. The lesson on determinants, their properties and Cramer’s rule interpreted the determinant of order two as a signed area, defined it in any order by recursion, proved its six properties by induction on the order, and used them to compute it by reduction. If this is so, each elementary operation multiplies the determinant by a nonzero number, and from this it followed that $\det A \neq 0$ if and only if $\operatorname{rank}(A) = n$ . The product theorem for determinants, $\det(AB) = \det A \det B$ , was proved there in order two by direct computation, and Cramer’s rule, proved in every order with the cofactors of a column, expressed each unknown as a quotient of determinants.

The lesson on the inverse matrix brought this topic to a close. It proved that the inverse is unique, that it exists if and only if the determinant is not zero, and that it is the adjugate divided by the determinant; that the inverse of a product reverses the order of the factors; and that each elementary operation is multiplication by an elementary matrix, whence the Gauss-Jordan method transforms $\left( A, I \right)$ into $\left( I, A^{-1} \right)$ without computing determinants. All this was gathered into a single theorem of equivalences, which ties together the four lessons before it; from it was deduced that it suffices to check one of the two products of the definition, and with elementary matrices the product theorem for determinants was proved in every order:

\exists A^{-1} \leftrightarrow \det A \neq 0 \leftrightarrow \operatorname{rank}(A) = n \leftrightarrow \left( AX = 0 \rightarrow X = 0 \right)

The geometry of matrices

The lesson on matrices as transformations of the plane gave that calculus a geometric meaning. By the columns theorem, the matrices of order two are exactly the linear transformations of the plane, and each one is determined by the images of the two standard basis vectors; with that principle the matrices of rotations, projections, reflections, dilations and shears were obtained. Composing transformations turned out to be multiplying their matrices, whence $R_\alpha R_\beta = R_{\alpha + \beta}$ and $S_\alpha S_\beta = R_{2(\alpha - \beta)}$ ; the determinant turned out to be the factor by which areas are multiplied, with a negative sign if the orientation is reversed; and the rotation of axes of the second-degree equation was written as the passage from $M$ to $R_\theta^{\mathsf{T}} M R_\theta$ , with the trace and the determinant as invariants.

The lesson on complex numbers as matrices applied that reading to multiplication by a complex number. The correspondence $M(a + bi) = aI + bJ$ is injective and preserves addition and multiplication; under it the squared modulus is the determinant, the conjugate is the transpose, the inverse is the inverse matrix and the polar form is a rotation followed by a dilation, $M(z) = r R_\theta$ . From this it followed that the formulas of Euler and De Moivre are the rule for composing rotations, that the matrices of the complex numbers are exactly those that commute with $J$ , and that Hamilton’s quaternions also admit a representation by matrices, whose product no longer commutes.

The structures

Finally, the lesson on algebraic structures isolated what is common. A group is a set with an associative operation, with an identity element and with inverses; in every group the identity element and the inverses are unique, cancellation holds and $(ab)^{-1} = b^{-1} a^{-1}$ , without using commutativity. Cyclic subgroups and cosets led to Lagrange’s theorem: the order of a subgroup divides the order of the group. Algebraic rings and fields added a second operation, and, starting from the theorem “The invertible remainders” of the Course I lesson on congruences, it was proved that $\mathbb{Z}_n$ is a field if and only if $n$ is prime. Isomorphisms, lastly, made precise the idea that two systems with the same table of operations are the same system.

Therefore, the unit forms a chain: composition motivates the product; the product allows systems to be written as equations $AX = B$ ; elimination solves them and the rank classifies them; the determinant decides uniqueness and the inverse expresses it; the composition of transformations gives the product back its geometric meaning; the complex numbers appear as a family of transformations closed under addition and composition; and the notion of group shows that the uniqueness of the inverse of a matrix, that of the inverse of a number and that of the rotation that undoes another are a single theorem. The following figure gathers the four segments into a single chain. Each node of the column is a definition or a theorem, numbered according to the logical order and joined by an arc to the earlier links that its proof uses; around it float the supports, that is, the principles and tools to which the chain resorts again and again, each joined by a solid line to the links that rest on it and by a dotted one to the link where it is established, except those that are admitted without proof or come from earlier units or from Course I, which are drawn as rings. Clicking a support highlights all the links that use it, and each link refers to the lesson in which it is proved.

Supports of the chain

AInduction. If a property holds in the first case and passes from each case to the one after it, it holds in all of them; proved in unit 1 of Course I, it serves here for double sums, elimination, powers and rotations. Admitted without proof in this unit.
BAssociativity of the product. $(AB)C = A(BC)$ holds whenever the products are defined, so that a product of several matrices can be grouped at will without altering the order of the factors. Established in: 2. Properties of the product.
CColumns theorem. Every linear transformation of the plane is that of a unique matrix, whose columns are the images of $\vec{e}_1$ and of $\vec{e}_2$ . Established in: 16. The columns of the matrix.
DSum formulas. The sine and cosine of a sum, of a difference and of the double angle, proved in unit 2, on analytic trigonometry. Admitted without proof in this unit.
EVectors in the plane. The distance from a point to a line, the orthogonal projection and the parallelism criterion, proved in unit 4 of Course I, on the analytic geometry of the plane. Admitted without proof in this unit.
FArea of the parallelogram. The area of a parallelogram is the product of a base and the corresponding height; it is admitted, as in elementary geometry, in the proof of the signed area theorem. Admitted without proof in this unit.
GRemainders and congruences. Division with remainder, congruence modulo $n$ , its compatibility with addition and multiplication, the classes of remainders and the theorem “The invertible remainders”, according to which $a$ has an inverse modulo $n$ if and only if $\operatorname{gcd}(a, n) = 1$ , proved in unit 1 of Course I, in the lessons on divisibility and on congruences. Admitted without proof in this unit.

Segment 1 The algebra of matrices and linear systems
- Define the matrix product from the composition of linear substitutions and write every linear system as an equation $AX = B$ .
- Prove associativity, distributivity and the neutrality of the identity matrix, and recognize that the product is not commutative and admits zero divisors.
- Prove that the transpose reverses the order of the factors and that the trace does not distinguish the order.
- Prove that the reduced row echelon form is unique and define the rank with it.
- Solve every linear system by the Gauss-Jordan method and classify it with the Rouché-Capelli theorem.
1. Matrix product. The entry $(i, j)$ of $AB$ is the sum of the products of row $i$ of $A$ and column $j$ of $B$ ; this gives the array of the composition of two linear substitutions, and every linear system is written as $AX = B$ .
  Proved in: Matrices and matrix operations.
2. Properties of the product. By interchanging the order of two sums, the matrix product is associative and distributive over addition, and the identity matrices are its identity elements; on the other hand, it is not commutative and admits zero divisors and nilpotent matrices. Moreover, $(AB)^{\mathsf{T}} = B^{\mathsf{T}} A^{\mathsf{T}}$ and $\operatorname{tr}(AB) = \operatorname{tr}(BA)$ , whence the equation $AB - BA = I$ has no solution.
  Uses: 1. Matrix product. Rests on: A (Induction). Proved in: Matrices and matrix operations.
3. Gauss-Jordan method. Elementary row operations transform a system into an equivalent one, and with them every matrix is reduced, after finitely many operations, to a reduced row echelon form.
  Uses: 1. Matrix product. Rests on: A (Induction). Proved in: Linear systems and the Gauss-Jordan method.
4. Uniqueness of the reduced form. Two reduced row echelon forms reached from the same matrix are equal, because their homogeneous systems have the same solutions; therefore the rank, the number of nonzero rows of any row echelon form, does not depend on the operations chosen.
  Uses: 3. Gauss-Jordan method. Rests on: A (Induction). Proved in: Linear systems and the Gauss-Jordan method.
5. Rouché-Capelli. The system $AX = B$ , with augmented matrix $M$ and $n$ unknowns, is consistent if and only if $\operatorname{rank}(A) = \operatorname{rank}(M)$ , and then it is determinate (it has exactly one solution) if the rank is $n$ and depends on $n - r$ free parameters if it is $r < n$ ; in particular, $AX = 0$ has nontrivial solutions if and only if $\operatorname{rank}(A) < n$ .
  Uses: 3. Gauss-Jordan method, 4. Uniqueness of the reduced form. Proved in: Linear systems and the Gauss-Jordan method.
Segment 2 The determinant and the inverse
- Interpret the determinant of order two as a signed area and define it in any order by recursion.
- Prove the properties of the determinant by induction on the order, compute it by reduction and decide with it the uniqueness of solutions.
- Characterize the invertible matrices and compute the inverse by the adjugate and by the Gauss-Jordan method.
- Gather into a single theorem the conditions equivalent to invertibility, and deduce from it the one-sided inverse and the product theorem for determinants.
1. Signed area. The absolute value of the determinant of the matrix with columns $\vec{u}$ and $\vec{v}$ is the area of the parallelogram they determine, and its sign indicates whether the rotation from $\vec{u}$ to $\vec{v}$ is counterclockwise or clockwise.
  Rests on: E (Vectors in the plane), D (Sum formulas), F (Area of the parallelogram). Proved in: Determinants: properties and Cramer’s rule.
2. Properties of the determinant. By induction on the order, starting from the cofactor expansion along the first row, the determinant is linear in each row, changes sign when two rows are interchanged, vanishes if a row is zero or if two rows are equal, does not change when a multiple of one row is added to another or when the matrix is transposed, equals the product of the diagonal in a triangular matrix, and can be expanded along any row or column.
  Rests on: A (Induction). Proved in: Determinants: properties and Cramer’s rule.
3. Determinant and rank. A square matrix of order $n$ has a nonzero determinant, that is, it is nonsingular, if and only if its rank is $n$ ; therefore $AX = 0$ has nonzero solutions if and only if $A$ is singular, that is, if $\det A = 0$ .
  Uses: 3. Gauss-Jordan method, 4. Uniqueness of the reduced form, 5. Rouché-Capelli, 7. Properties of the determinant. Proved in: Determinants: properties and Cramer’s rule.
4. Cramer’s rule. If $D = \det A \neq 0$ , the system $AX = B$ of $n$ equations in $n$ unknowns has a unique solution, $x_k = \frac{D_k}{D}$ , where $D_k$ results from replacing column $k$ by the column of constant terms; it is proved in every order with the cofactors of column $k$ .
  Uses: 2. Properties of the product, 5. Rouché-Capelli, 7. Properties of the determinant, 8. Determinant and rank. Proved in: Determinants: properties and Cramer’s rule.
5. Uniqueness of the inverse. A square matrix has at most one inverse: if $AB = BA = I$ and $AD = DA = I$ , then $B = D$ .
  Rests on: B (Associativity of the product). Proved in: The inverse matrix.
6. Determinant and invertibility. A square matrix $A$ is invertible if and only if $\det A \neq 0$ , that is, if it is nonsingular, and then its inverse is the adjugate divided by the determinant; necessity is obtained through the rank, without using the determinant of a product, and sufficiency through the lemma on alien cofactors.
  Uses: 5. Rouché-Capelli, 7. Properties of the determinant, 8. Determinant and rank. Rests on: B (Associativity of the product). Proved in: The inverse matrix.
7. Properties of the inverse. If $A$ and $B$ are invertible, so are $AB$ , $A^{\mathsf{T}}$ , $cA$ with $c \neq 0$ and $A^m$ , and in particular $(AB)^{-1} = B^{-1} A^{-1}$ .
  Uses: 2. Properties of the product, 10. Uniqueness of the inverse. Rests on: B (Associativity of the product), A (Induction). Proved in: The inverse matrix.
8. Inverse by Gauss-Jordan. Each elementary operation is multiplication by an invertible elementary matrix; if the reduced row echelon form of $A$ is $I$ , the operations transform $\left( A, I \right)$ into $\left( I, A^{-1} \right)$ and $A$ is a product of elementary matrices, and if it is not, $A$ is not invertible.
  Uses: 3. Gauss-Jordan method, 4. Uniqueness of the reduced form, 12. Properties of the inverse. Rests on: B (Associativity of the product). Proved in: The inverse matrix.
9. Characterizations and one-sided inverse. For a square matrix $A$ of order $n$ the following are equivalent: that it is invertible, that $\det A \neq 0$ , that each system $AX = D$ has a unique solution, that $AX = 0$ has only the trivial solution, that $\operatorname{rank}(A) = n$ and that its reduced row echelon form is the identity. It follows that, if $AB = I$ or $BA = I$ , then $B = A^{-1}$ .
  Uses: 5. Rouché-Capelli, 4. Uniqueness of the reduced form, 11. Determinant and invertibility, 13. Inverse by Gauss-Jordan. Rests on: B (Associativity of the product). Proved in: The inverse matrix.
10. Determinant of the product. For all square matrices $A$ and $B$ of the same order, $\det(AB) = \det A \det B$ holds: it is proved with elementary matrices if $A$ is invertible, and through the rank if it is not.
  Uses: 7. Properties of the determinant, 8. Determinant and rank, 13. Inverse by Gauss-Jordan, 14. Characterizations and one-sided inverse. Rests on: A (Induction). Proved in: The inverse matrix.
Segment 3 The geometry of matrices
- Identify the matrices of order two with the linear transformations of the plane and obtain the matrices of rotations, projections and reflections.
- Translate the composition of transformations into the matrix product, and the determinant into the area factor.
- Write the rotation of axes in matrix form, with the trace and the determinant as invariants.
- Represent the complex numbers as matrices, with the modulus, the conjugate, the inverse and the polar form.
1. The columns of the matrix. Every matrix transformation is linear, and every linear transformation of the plane is that of a unique matrix, the one whose columns are $T(\vec{e}_1)$ and $T(\vec{e}_2)$ .
  Uses: 2. Properties of the product. Proved in: Matrices as transformations of the plane.
2. Rotations, projections and reflections. The rotation by the angle $\theta$ about the origin, the projection onto a line through the origin and the reflection in it are linear transformations, with matrices $R_\theta$ , $P_\alpha$ and $S_\alpha$ .
  Rests on: C (Columns theorem), D (Sum formulas), E (Vectors in the plane). Proved in: Matrices as transformations of the plane.
3. Composition and product. If $T$ is the transformation with matrix $A$ and $U$ the one with matrix $B$ , the composition $T \circ U$ is the transformation with matrix $AB$ .
  Rests on: B (Associativity of the product), C (Columns theorem). Proved in: Matrices as transformations of the plane.
4. Composition of rotations and reflections. The identities $R_\alpha R_\beta = R_{\alpha + \beta}$ , $R_\theta^{-1} = R_\theta^{\mathsf{T}}$ , $R_\theta^n = R_{n\theta}$ and $S_\alpha S_\beta = R_{2(\alpha - \beta)}$ hold.
  Uses: 17. Rotations, projections and reflections, 18. Composition and product. Rests on: D (Sum formulas), A (Induction). Proved in: Matrices as transformations of the plane.
5. Determinant as an area scale factor. The transformation with matrix $A$ takes the unit square to the parallelogram of its columns and multiplies areas by $\abs{\det A}$ , which is admitted for general regions; it preserves orientation if $\det A > 0$ and reverses it if $\det A < 0$ .
  Uses: 6. Signed area. Rests on: C (Columns theorem). Proved in: Matrices as transformations of the plane.
6. Invertible transformations. The transformation with matrix $A$ is bijective if and only if $\det A \neq 0$ , and then its inverse is the one with matrix $A^{-1}$ ; if $\det A = 0$ , its image is contained in a line through the origin.
  Uses: 11. Determinant and invertibility, 18. Composition and product. Rests on: E (Vectors in the plane). Proved in: Matrices as transformations of the plane.
7. Rotation of axes in matrix form. When the axes are rotated by the angle $\theta$ , the symmetric matrix $M$ of a quadratic form becomes $R_\theta^{\mathsf{T}} M R_\theta$ , which has the same trace and the same determinant as $M$ .
  Uses: 2. Properties of the product, 7. Properties of the determinant, 15. Determinant of the product, 19. Composition of rotations and reflections. Proved in: Matrices as transformations of the plane.
8. Complex numbers as matrices. The correspondence $M(a + bi) = aI + bJ$ is injective and preserves addition and multiplication, and $J$ , the matrix of $i$ , is the quarter-turn rotation, whose square is $-I$ .
  Uses: 1. Matrix product, 17. Rotations, projections and reflections. Proved in: Complex numbers as matrices.
9. Modulus, conjugate and inverse. The determinant of $M(z)$ is $\abs{z}^2$ , the matrix of the conjugate is the transpose of $M(z)$ and, if $z \neq 0$ , the matrix of $z^{-1}$ is the inverse of $M(z)$ .
  Uses: 10. Uniqueness of the inverse, 20. Determinant as an area scale factor, 23. Complex numbers as matrices. Proved in: Complex numbers as matrices.
10. Polar form and De Moivre. If $z = r\left( \cos \theta + i \sin \theta \right)$ , then $M(z) = r R_\theta$ , a rotation followed by a dilation; and from $R_\theta^n = R_{n\theta}$ follows De Moivre’s formula for every integer exponent.
  Uses: 19. Composition of rotations and reflections, 23. Complex numbers as matrices, 24. Modulus, conjugate and inverse. Rests on: A (Induction). Proved in: Complex numbers as matrices.
Segment 4 The structures
- Define groups and prove their elementary properties without using commutativity.
- Study cyclic subgroups and prove Lagrange’s theorem.
- Define algebraic rings and fields and decide when the remainders $\mathbb{Z}_n$ form a field.
- Make precise, with isomorphisms, when two groups are the same structure.
1. Properties of groups. In every group the identity element and the inverse of each element are unique, cancellation on each side holds and $(ab)^{-1} = b^{-1} a^{-1}$ , without using commutativity.
  Proved in: Algebraic structures: groups, rings and fields.
2. Cyclic subgroup. In a finite group, every element $g$ has an order $k$ , $g^m = e$ holds if and only if $k$ divides $m$ , and the powers $e, g, \ldots, g^{k - 1}$ form a subgroup of $k$ elements.
  Uses: 26. Properties of groups. Rests on: G (Remainders and congruences). Proved in: Algebraic structures: groups, rings and fields.
3. Lagrange’s theorem. The order of a subgroup of a finite group divides the order of the group, because the group splits into disjoint cosets with as many elements as the subgroup.
  Uses: 26. Properties of groups. Proved in: Algebraic structures: groups, rings and fields.
4. The remainders form a field. For $n \geq 2$ , the remainders $\mathbb{Z}_n$ form a field if $n$ is prime, because by the theorem “The invertible remainders” every nonzero remainder has an inverse; if $n$ is composite, they have zero divisors and do not form one.
  Rests on: G (Remainders and congruences). Proved in: Algebraic structures: groups, rings and fields.
5. What an isomorphism preserves. An isomorphism of groups takes the identity element to the identity element, the inverse of each element to the inverse of its image and each element to one of the same order, and it preserves commutativity.
  Uses: 26. Properties of groups, 27. Cyclic subgroup. Rests on: A (Induction). Proved in: Algebraic structures: groups, rings and fields.

Toward the geometry of space. The chain does not stop here: in the following unit, the determinant of order three gives the cross product, the scalar triple product and the volume of a parallelepiped, and the rank and the inverse matrix decide and compute the intersections of lines and planes, so that the algebra of this unit becomes the instrument of the geometry of space.