When a matrix or transformation can be undone
A linear transformation scrambles every vector of space. When can the scrambling be undone, so that each output tells you exactly which input it came from, and what does the undoing look like?
Where you are 9 in Matrices as linear transformations
Why this exists
Paqari, Tayen and Wayta run a secret-message club. Each letter becomes a number, \text{A} = 1 up to \text{Z} = 26, with 0 for a space. A message is cut into pairs, and each pair \mathbf{x} is sent as K\mathbf{x} for a 2 \times 2 key matrix K the members share. Encoding is the Linear transformation T(\mathbf{x}) = K\mathbf{x}.
A key is useful only if a second transformation takes each sent pair back to its message, and some keys fail. This lesson says exactly which linear transformations can be undone, proves that the undoing is again linear, and shows why the matrix must be square.
Definition
A transformation T: \mathbb{R}^n \to \mathbb{R}^m is invertible when some transformation S: \mathbb{R}^m \to \mathbb{R}^n undoes it from both sides:
Then S is the inverse of T, written T^{-1}. Recall that T is one-to-one when different inputs give different outputs, and onto when every vector of \mathbb{R}^m is an output, that is, when its image is all of \mathbb{R}^m.
For matrices the definition is the one from Inverse of a 2 by 2 matrix, and solving with it: an n \times n matrix A is invertible when some n \times n matrix A^{-1} has AA^{-1} = A^{-1}A = I. A square matrix that is not invertible is singular.
Intuition
Decoding fails in two ways: two messages sent as one pair (not one-to-one), or a pair that comes from no message (not onto).
For a linear map the first failure has a simple test. By the Equal outputs result of Kernel, two inputs collide exactly when their difference lands on \mathbf{0}, so T is one-to-one exactly when nothing but \mathbf{0} lands on \mathbf{0}. A key with a nonzero kernel vector squashes the plane along that direction onto a line, as B in the figure does, and What the determinant means says a map flattens space exactly when its determinant is 0.
For a square matrix the two failures coincide.
Results
Invertible means one-to-one and onto. A transformation has an inverse exactly when it is both, and then the inverse is unique.
The inverse of a linear map is linear. If T(\mathbf{x}) = A\mathbf{x} is invertible, then T^{-1} is linear, A is square and invertible, and the matrix of T^{-1} is A^{-1}.
The square test. For an n \times n matrix A and T(\mathbf{x}) = A\mathbf{x}, these say the same thing:
- T is invertible (equivalently, A is invertible);
- \ker A = \{\mathbf{0}\}: nothing but \mathbf{0} lands on \mathbf{0};
- \operatorname{im} A = \mathbb{R}^n: every vector is an output;
- \det A \neq 0.
One product is enough. If A and B are n \times n and AB = I, then BA = I as well, so B = A^{-1}.
Only square matrices are invertible. An m \times n matrix with m \neq n has no two-sided inverse.
The The invertible matrix theorem gathers many more conditions equivalent to these four.
Why it is true
One-to-one and onto. If S undoes T and T(\mathbf{u}) = T(\mathbf{v}), applying S gives \mathbf{u} = \mathbf{v}; and any \mathbf{y} is the output T(S(\mathbf{y})). Conversely, if T is one-to-one and onto, each \mathbf{y} is the output of exactly one input; let S(\mathbf{y}) be that input. Then T(S(\mathbf{y})) = \mathbf{y}, and S(T(\mathbf{x})) = \mathbf{x} because \mathbf{x} is the one input with output T(\mathbf{x}). Any inverse must send \mathbf{y} to that same input, so it is unique.
The inverse is linear. Let S = T^{-1}. Linearity of T gives
and since T is one-to-one, S(\mathbf{u}) + S(\mathbf{v}) = S(\mathbf{u} + \mathbf{v}). In the same way T(cS(\mathbf{u})) = c\mathbf{u} = T(S(c\mathbf{u})) gives cS(\mathbf{u}) = S(c\mathbf{u}). So S is linear and has a matrix B, with columns S(\mathbf{e}_1), \dots, S(\mathbf{e}_m) (Finding the matrix of a transformation). By Composing transformations as a matrix product the identity map T \circ S has matrix AB, so AB = I, and likewise S \circ T gives BA = I. That A is square is the last result, proved below, so B = A^{-1}.
The square test. (1) gives (2), since an invertible map is one-to-one. Next count pivots. \ker A = \{\mathbf{0}\} exactly when every column has a pivot (Kernel), and \operatorname{im} A = \mathbb{R}^n exactly when every row has one (Image). Each pivot uses one row and one column, so with n rows and n columns, the pivots fill every column exactly when they fill every row. So (2) and (3) hold together, and together they are one-to-one and onto, which is (1). Finally, \det A = 0 exactly when A flattens \mathbb{R}^n into a lower-dimensional subspace, that is, exactly when \operatorname{im} A \neq \mathbb{R}^n; so (3) and (4) agree. What the determinant means proves this for the plane; for larger n it is taken here without proof.
One product is enough. If AB = I, any \mathbf{y} equals A(B\mathbf{y}), so \operatorname{im} A = \mathbb{R}^n. By the square test A is invertible, and B = A^{-1}(AB) = A^{-1}.
Only square matrices. If A is m \times n and \mathbf{x} \mapsto A\mathbf{x} is invertible, then \ker A = \{\mathbf{0}\} and \operatorname{im} A = \mathbb{R}^m. Rank and nullity, used here without proof, says \dim \operatorname{im} A + \dim \ker A = n, so m + 0 = n.
Worked examples
Encoding and decoding with a key
Tayen picks the key A = \begin{bmatrix} 4 & 3 \\ 5 & 4 \end{bmatrix}. Encode the word GO, show that every message can be decoded, and decode the result.
SolutionG is 7 and O is 15, so
\det A = 16 - 15 = 1 \neq 0, so by the square test the map is invertible: no two messages collide and every pair decodes. By Inverse of a 2 by 2 matrix, and solving with it,
which is GO. Since \det A = 1, the decoder has integer entries.
A key that cannot be undone
Wayta proposes B = \begin{bmatrix} 2 & 4 \\ 1 & 2 \end{bmatrix}. Show that two different messages are sent as the same pair, and describe what the receiver learns.
Solution\det B = 4 - 4 = 0, so B is singular. Indeed
So “B, space” and “space, A” are sent identically. Their difference (2, -1) is in the kernel, since 2 \cdot 2 + 4 \cdot (-1) = 0, and \ker B = \operatorname{span}\{(2, -1)\}. In general
so the receiver learns only the number x + 2y. Every output lies on the line \operatorname{im} B = \operatorname{span}\{(2, 1)\}, so the map is not onto either: (5, 3) comes from no message.
A three-letter key decided by its kernel
The club moves to triples. Decide which of these keys can be undone:
By the square test it is enough to find each kernel. For C, subtract 2 times row 1 from row 2 and row 1 from row 3; both new rows are (0, 1, -3), so row 3 becomes zero. Then x_3 = t is free, x_2 = 3t and x_1 = -x_2 - 2x_3 = -5t:
C cannot be undone. For instance “E, space, space” = (5, 0, 0) and “space, C, A” = (0, 3, 1) differ by -(-5, 3, 1), and both are sent as (5, 10, 5).
For D the same two steps give rows (0, 1, -3) and (0, 1, -2), whose difference is (0, 0, 1). All three columns have pivots, so \ker D = \{\mathbf{0}\} and D is invertible. By Determinants by cofactor expansion along row 1, \det C = -5 + 3 + 2 = 0 and \det D = -2 + 1 + 2 = 1.
One product is enough
Wayta claims the decoder for the key D of Example 3 is
Check the claim cheaply, then decode the received triple (44, 29, 5).
SolutionBoth are square, so one product suffices. Row 1 of D, (1, 1, 2), against the columns of L gives -2 + 1 + 2 = 1, 4 - 2 - 2 = 0, -5 + 3 + 2 = 0, and rows 2 and 3 give (0, 1, 0) and (0, 0, 1). So DL = I, hence LD = I too and L = D^{-1}. (Finding L from scratch is Finding an inverse by row reducing A next to I.) Then
the word CAT. Check: D(3, 1, 20) = (44, 29, 5).
A tall key that catches errors
Tayen sends each pair as a triple, with E = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 2 & 3 \end{bmatrix}. Show that no two messages collide but E has no two-sided inverse, and decode (5, 7, 12) and (5, 7, 11) if possible.
SolutionThe columns (1, 1, 2) and (1, 2, 3) are not parallel, so they are independent and \ker E = \{\mathbf{0}\}: the map is one-to-one. It is not onto: E(x, y) = (x + y,\ x + 2y,\ 2x + 3y), whose third entry is always the sum of the first two, so the image is a plane in \mathbb{R}^3. Being 3 \times 2, E has no two-sided inverse.
It does have a left inverse, which is all decoding needs. With L = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 1 & 0 \end{bmatrix}, LE = I, but
(5, 7, 12) passes the test 5 + 7 = 12, and L(5, 7, 12) = (10 - 7,\ -5 + 7) = (3, 2), the message CB; check E(3, 2) = (5, 7, 12). (5, 7, 11) fails the test, so no message produces it: an error crept in on the way.
A chain with one bad link
Paqari encodes with A of Example 1, and then Wayta encodes the result again with B of Example 2. Can the chain be undone, and which messages collide?
SolutionThe chain \mathbf{x} \mapsto B(A\mathbf{x}) has matrix
and \det(BA) = 308 - 308 = 0, so it cannot be undone. Its kernel needs no row reduction: BA\mathbf{x} = \mathbf{0} means A\mathbf{x} is in \ker B = \operatorname{span}\{(2, -1)\}, so \mathbf{x} is a multiple of
Check: 28 \cdot 11 - 22 \cdot 14 = 0. Messages collide exactly when they differ by a multiple of (11, -14); “K, space” = (11, 0) and “space, N” = (0, 14) are both sent as (308, 154).
Boundaries
- Square only, for a two-sided inverse. A tall matrix can be one-to-one with a left inverse (Example 5); a wide one can be onto with a right inverse (Exercise 12). Neither is invertible, and a one-sided inverse need not be unique.
- One product is enough only for square matrices. For a 2 \times 3 matrix A and a 3 \times 2 matrix B, AB = I can hold while BA \neq I (Exercise 18).
- The kernel test needs linearity. For x \mapsto x^2, only 0 goes to 0, yet 1 and -1 collide. And a map can be invertible without being linear, such as the slide (x, y) \mapsto (x + 1, y) (Exercise 19).
- Integer decoding. A key with integer entries and \det \neq 0 always decodes, but its decoder has integer entries only when \det = \pm 1 (Exercise 20).
Where this goes next
The square test is the start of the The invertible matrix theorem, which adds independent columns, reduced form I and more. Turned around, it drives eigenvalues: The characteristic equation and finding eigenvalues looks for the numbers \lambda that give A - \lambda I a nonzero kernel. And an invertible matrix is exactly a change of basis, as in Coordinates in a basis and change of basis.
Exercises
Deciding whether a key can be undone
- Is \mathbf{x} \mapsto M\mathbf{x} invertible for M = \begin{bmatrix} 3 & -2 \\ 6 & -4 \end{bmatrix}? Find \ker M.
- Show that \begin{bmatrix} 5 & 2 \\ 7 & 3 \end{bmatrix} is invertible and find its inverse.
- For which numbers k is \begin{bmatrix} k & 3 \\ 3 & k \end{bmatrix} invertible? For the positive k that fails, find the kernel.
- Decide by its kernel whether \begin{bmatrix} 1 & 2 & 1 \\ 0 & 1 & 1 \\ 1 & 3 & 2 \end{bmatrix} is invertible.
- Decide by its kernel whether \begin{bmatrix} 1 & 0 & 2 \\ 2 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} is invertible, and give its determinant.
- Is T(x, y) = (x - y,\ y - x) invertible? Describe its kernel and image.
Inverses of maps and decoding
- Find the inverse of T(x, y) = (-2y,\ x) as a formula and as a matrix.
- Find T^{-1} and its matrix for T(x_1, x_2, x_3) = (x_1 + x_3,\ x_2,\ x_3 - x_2).
- Tayen’s new key is \begin{bmatrix} 2 & 3 \\ 3 & 5 \end{bmatrix}. (a) Encode UP. (b) Decode the received pair (101, 164).
- Wayta’s new key is \begin{bmatrix} 3 & 6 \\ 1 & 2 \end{bmatrix}. Show that (2, 1) and (0, 2) are sent as the same pair, find the kernel, and find a third message sent as that pair.
- With the key of Exercise 10, which messages could have produced the received pair (9, 3), and which produced (10, 4)?
Shapes and chains
- Let A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}. Find a nonzero vector in \ker A, and show that R = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{bmatrix} has AR = I.
- For F = \begin{bmatrix} 1 & 0 \\ 2 & 1 \\ 0 & 1 \end{bmatrix}, decide whether (3, 7, 1) and (3, 7, 2) are outputs, and for each output find the message.
- Let K_1 = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix} and K_2 = \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}. Find K_2 K_1, decide whether it is invertible, and find its kernel as K_1^{-1} applied to \ker K_2.
- A club encodes triples of letters as pairs with a 2 \times 3 key. Explain why some two different messages are always sent as the same pair, whatever the key.
Reasoning
- Let A and B be invertible n \times n matrices. Use kernels to show that BA is invertible.
- Show that a square matrix A with A^2 = 0 is not invertible.
- Explain why, for a 2 \times 3 matrix A and a 3 \times 2 matrix B, the 3 \times 3 product BA is never I, even when AB = I.
- Show that T(x, y) = (x + 1,\ y) has an inverse function, and explain why this does not fit the theorem that the inverse of a linear map is linear.
- Let A be 2 \times 2 and invertible with integer entries. Show that A^{-1} has integer entries if \det A = \pm 1, and that if both A and A^{-1} have integer entries then \det A = \pm 1.
Answers
- Not invertible: \det M = -12 + 12 = 0. \ker M = \operatorname{span}\{(2, 3)\}: row 2 is twice row 1, and 3x - 2y = 0 gives x = 2t, y = 3t.
- \det = 15 - 14 = 1 \neq 0; swap and negate: \begin{bmatrix} 3 & -2 \\ -7 & 5 \end{bmatrix}.
- \det = k^2 - 9, so invertible for every k except k = 3 and k = -3. At k = 3 both rows are (3, 3) and the kernel is \operatorname{span}\{(1, -1)\}.
- Not invertible. Row 3 minus row 1 is (0, 1, 1), equal to row 2, so column 3 gets no pivot: \ker = \operatorname{span}\{(1, -1, 1)\}, from x_3 = t, x_2 = -t, x_1 = -2x_2 - x_3 = t.
- Invertible. R_2 - 2R_1 gives (0, 1, -4), then R_3 - R_2 gives (0, 0, 5): three pivots, kernel \{\mathbf{0}\}. The determinant is 5.
- No. \ker T = \operatorname{span}\{(1, 1)\}, the line y = x, and \operatorname{im} T = \operatorname{span}\{(1, -1)\}, since every output is (x - y)(1, -1).
- T^{-1}(u, v) = (v,\ -\tfrac12 u), from u = -2y and v = x. Matrix \begin{bmatrix} 0 & 1 \\ -\tfrac12 & 0 \end{bmatrix}, the inverse of \begin{bmatrix} 0 & -2 \\ 1 & 0 \end{bmatrix}.
- Solving T(\mathbf{x}) = \mathbf{y} gives x_2 = y_2, x_3 = y_3 + y_2, x_1 = y_1 - y_2 - y_3, a linear map T^{-1}(\mathbf{y}) = (y_1 - y_2 - y_3,\ y_2,\ y_2 + y_3), with matrix \begin{bmatrix} 1 & -1 & -1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}.
- (a) UP is (21, 16), sent as (42 + 48,\ 63 + 80) = (90, 143). (b) The determinant is 1 and the inverse \begin{bmatrix} 5 & -3 \\ -3 & 2 \end{bmatrix} gives (505 - 492,\ -303 + 328) = (13, 25), the word MY.
- Both are sent as (12, 4). The kernel is \operatorname{span}\{(2, -1)\}, from x + 2y = 0, and (2, 1) - (0, 2) = (2, -1). A third: (4, 0) = (2, 1) + (2, -1).
- Every output is (x + 2y)(3, 1). For (9, 3), x + 2y = 3 with entries from 0 to 26: the messages (3, 0) and (1, 1), “C, space” and “AA”. (10, 4) is not a multiple of (3, 1), so no message produced it.
- (-1, -1, 1): both rows give -1 + 1 = 0. AR = I because A times the columns of R gives its first two columns, \mathbf{e}_1 and \mathbf{e}_2.
- F(x, y) = (x,\ 2x + y,\ y), so outputs satisfy b_2 = 2b_1 + b_3. (3, 7, 1) does, and comes from (3, 1). (3, 7, 2) does not, since 6 + 2 \neq 7.
- K_2K_1 = \begin{bmatrix} 4 & 3 \\ 8 & 6 \end{bmatrix}, determinant 24 - 24 = 0: not invertible. \ker K_2 = \operatorname{span}\{(2, -1)\} and K_1^{-1} = \begin{bmatrix} 1 & -1 \\ -1 & 2 \end{bmatrix} sends (2, -1) to (3, -4), so \ker(K_2K_1) = \operatorname{span}\{(3, -4)\}.
- A 2 \times 3 matrix has at most 2 pivots for 3 columns, so a free variable gives a kernel vector \mathbf{k} \neq \mathbf{0}, and \mathbf{x} and \mathbf{x} + \mathbf{k} are sent alike.
- If BA\mathbf{x} = \mathbf{0}, then A\mathbf{x} is in \ker B = \{\mathbf{0}\}, so A\mathbf{x} = \mathbf{0} and \mathbf{x} = \mathbf{0} since \ker A = \{\mathbf{0}\}. So \ker(BA) = \{\mathbf{0}\}, and the square test makes BA invertible.
- If A were invertible, A = A^{-1}A^2 = A^{-1}0 = 0, but the zero matrix sends everything to \mathbf{0} and is not invertible.
- A is wide, so some \mathbf{k} \neq \mathbf{0} has A\mathbf{k} = \mathbf{0}. Then BA\mathbf{k} = \mathbf{0} \neq \mathbf{k} = I\mathbf{k}, so BA \neq I.
- S(x, y) = (x - 1,\ y) undoes it from both sides. No conflict: T is not linear, since T(\mathbf{0}) = (1, 0) \neq \mathbf{0}, so the theorem does not apply.
- If \det A = \pm 1, the formula \displaystyle A^{-1} = \frac{1}{\det A}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix} has integer entries. Conversely, \det A \cdot \det A^{-1} = \det(AA^{-1}) = 1 by the product rule of What the determinant means. Both determinants are integers, built from products and differences of integer entries, and two integers with product 1 are both 1 or both -1.