studyhubDiscrete Structures III

Notes / Unit 3 · Module 2 · Exam 1 · §2.3

The Inverse of a Matrix

The inverse of a square matrix A is the matrix A⁻¹ that undoes it: AA⁻¹ = A⁻¹A = I. The exam asks you to decide whether A⁻¹ exists, find it with the ad − bc formula or by row-reducing [A | I], use its properties, and solve Ax = b as x = A⁻¹b.

3.1Matrices and their inverses

An n × n matrix A is invertible (or nonsingular) when there is an n × n matrix B with AB = BA = Iₙ, where Iₙ is the identity of order n. B is the (multiplicative) inverse of A. A matrix with no inverse is noninvertible (or singular).

  • Nonsquare matrices have no inverse. If A is m × n and B is n × m, AB is m × m and BA is n × n, so AB = BA is impossible.
  • Not every square matrix has one. [1 2; 2 4] has none, for instance.
  • The inverse is unique (Theorem 2.7): if AB = I and AC = I, then B = BI = B(AC) = (BA)C = IC = C. That is why it gets its own name, A⁻¹.

Worked example

Example 1: A = [1 2; 1 1], B = [−1 2; 1 −1]

  1. 1AB = [1(−1) + 2(1) 1(2) + 2(−1); 1(−1) + 1(1) 1(2) + 1(−1)] = [1 0; 0 1].
  2. 2BA = [−1(1) + 2(1) −1(2) + 2(1); 1(1) − 1(1) 1(2) − 1(1)] = [1 0; 0 1].
  3. 3Both products are I, so B = A⁻¹. Likewise A is the inverse of B.

Exercise 1 works the same way: A = [−1 2; −1 1] and B = [1 −2; 1 −1] give AB = I and BA = I.

3.2The inverse of a 2 × 2 matrix

The slides first find an inverse from the definition. For A = [1 4; −1 −3], look for X = [a b; c d] with AX = I:

Worked example

Example 2: A = [1 4; −1 −3]

  1. 1AX = [a + 4c b + 4d; −a − 3c −b − 3d], and this must equal [1 0; 0 1].
  2. 2Matching entries: a + 4c = 1, −a − 3c = 0 and b + 4d = 0, −b − 3d = 1.
  3. 3Solving: a = −3, c = 1, b = −4, d = 1.
  4. 4A⁻¹ = [−3 −4; 1 1]. Check: AA⁻¹ = I.

Doing that in general gives a formula. A 2 × 2 matrix is invertible if and only if ad − bc ≠ 0, and then:

A = [a b; c d] ⇒ A⁻¹ = 1/(ad − bc) · [d −b; −c a]

ad − bc
main diagonal product minus the other diagonal product (the determinant of A)
[d −b; −c a]
swap a and d, change the signs of b and c

If ad − bc = 0, A is singular: there is nothing to divide by.

Worked example

Exercise 4: if possible, find the inverse

  1. 1A = [3 −1; −2 2]: ad − bc = (3)(2) − (−1)(−2) = 6 − 2 = 4 ≠ 0.
  2. 2A⁻¹ = 1/4 · [2 1; 2 3] = [1/2 1/4; 1/2 3/4].
  3. 3B = [3 −1; −6 2]: ad − bc = (3)(2) − (−1)(−6) = 6 − 6 = 0, so B has no inverse. (Its second row is −2 times the first.)

3.3Finding A⁻¹ by Gauss-Jordan elimination

For a square matrix A of order n:

  1. Write the n × 2n matrix [A | I]: A on the left, the identity on the right. This is called adjoining I to A.
  2. Row-reduce the whole matrix until the left block is I. The result is [I | A⁻¹]. If the left block can't be made I (a row of zeros appears on the left), A is singular.
  3. Check by multiplying: AA⁻¹ = I = A⁻¹A.

Worked example

Exercise 2: A = [1 −1 0; 1 0 −1; −6 2 3]

  1. 1Start from [A | I] (see the matrices below).
  2. 2R2 → R2 − R1 and R3 → R3 + 6R1 clear the first column: rows become [0 1 −1 | −1 1 0] and [0 −4 3 | 6 0 1].
  3. 3R3 → R3 + 4R2 gives [0 0 −1 | 2 4 1]; then R3 → −R3 gives [0 0 1 | −2 −4 −1].
  4. 4R2 → R2 + R3 gives [0 1 0 | −3 −3 −1].
  5. 5R1 → R1 + R2 gives [1 0 0 | −2 −3 −1]. The left block is I, so A⁻¹ = [−2 −3 −1; −3 −3 −1; −2 −4 −1].
[  1  −1   0  | 1  0  0 ]
[  1   0  −1  | 0  1  0 ]
[ −6   2   3  | 0  0  1 ]

→

[ 1  0  0  | −2  −3  −1 ]
[ 0  1  0  | −3  −3  −1 ]
[ 0  0  1  | −2  −4  −1 ]
[A | I] at the start and [I | A⁻¹] at the end

Worked example

Exercise 3: show A = [1 2 0; 3 −1 2; −2 3 −2] has no inverse

  1. 1R2 → R2 − 3R1 gives [0 −7 2 | −3 1 0]; R3 → R3 + 2R1 gives [0 7 −2 | 2 0 1].
  2. 2R3 → R3 + R2 gives [0 0 0 | −1 1 1].
  3. 3The left block now has a row of zeros, so it can never become I. A is singular.

3.4Properties of inverses

Theorem 2.8. If A is invertible, k is a positive integer and c is a nonzero scalar, then A⁻¹, Aᵏ, cA and Aᵀ are invertible, and:

RuleIn words
(A⁻¹)⁻¹ = AInverting twice gets you back to A
(Aᵏ)⁻¹ = A⁻¹A⁻¹ ⋯ A⁻¹ = (A⁻¹)ᵏk factors; written A⁻ᵏ
(cA)⁻¹ = (1/c)A⁻¹The scalar inverts too
(Aᵀ)⁻¹ = (A⁻¹)ᵀTransposing and inverting can be done in either order

Worked example

Exercise 5: A⁻² two ways, for A = [1 1; 2 4]

  1. 1ad − bc = 4 − 2 = 2, so A⁻¹ = 1/2 · [4 −1; −2 1] = [2 −1/2; −1 1/2].
  2. 2Way 1, (A⁻¹)²: [2 −1/2; −1 1/2][2 −1/2; −1 1/2] = [9/2 −5/4; −5/2 3/4].
  3. 3Way 2, (A²)⁻¹: A² = [3 5; 10 18], ad − bc = 54 − 50 = 4, so (A²)⁻¹ = 1/4 · [18 −5; −10 3] = [9/2 −5/4; −5/2 3/4].
  4. 4Both give the same matrix.

Theorem 2.9, the inverse of a product. If A and B are invertible of order n, then AB is invertible and

(AB)⁻¹ = B⁻¹A⁻¹

Check: (AB)(B⁻¹A⁻¹) = A(BB⁻¹)A⁻¹ = AIA⁻¹ = AA⁻¹ = I. It extends to more factors: (ABC)⁻¹ = C⁻¹B⁻¹A⁻¹.

Worked example

Exercise 6: A = [1 3 3; 1 4 3; 1 3 4], B = [1 2 3; 1 3 3; 2 4 3]

  1. 1Gauss-Jordan gives A⁻¹ = [7 −3 −3; −1 1 0; −1 0 1] and B⁻¹ = [1 −2 1; −1 1 0; 2/3 0 −1/3].
  2. 2(AB)⁻¹ = B⁻¹A⁻¹ = [8 −5 −2; −8 4 3; 5 −2 −7/3].
  3. 3No need to multiply AB out and invert a new 3 × 3.

3.5Cancellation

Theorem 2.10. If C is invertible:

Right cancellation
If AC = BC, then A = B. Multiply both sides on the right by C⁻¹.
Left cancellation
If CA = CB, then A = B. Multiply both sides on the left by C⁻¹.

The same move solves matrix equations: from AXB = C with A and B invertible, multiply on the left by A⁻¹ and on the right by B⁻¹ to get X = A⁻¹CB⁻¹.

3.6Solving Ax = b with A⁻¹

Theorem 2.11. If A is invertible, the system Ax = b has exactly one solution:

x = A⁻¹b

A
the n × n coefficient matrix
b
the column of constants

Multiply Ax = b on the left by A⁻¹: A⁻¹Ax = A⁻¹b, so x = A⁻¹b.

Worked example

Exercise 7: 2x + 3y + z = b₁, 3x + 3y + z = b₂, 2x + 4y + z = b₃

  1. 1The coefficient matrix A = [2 3 1; 3 3 1; 2 4 1] has A⁻¹ = [−1 1 0; −1 0 1; 6 −2 −3]. Find it once.
  2. 2(a) b = (−1, 1, −2): x = A⁻¹b = (1 + 1, 1 − 2, −6 − 2 + 6) = (2, −1, −2).
  3. 3(b) b = (4, 8, 5): x = A⁻¹b = (−4 + 8, −4 + 5, 24 − 16 − 15) = (4, 1, −7).
  4. 4(c) b = (0, 0, 0): x = A⁻¹0 = (0, 0, 0), the trivial solution only.

This pays off when one coefficient matrix meets several right-hand sides: invert once, then each system is a single multiplication.

3.7Application: the inverse in cryptography

The course's activity uses an invertible matrix as the key of a Hill cipher (Larson §2.5). Each character becomes a number, the numbers are grouped into uncoded row matrices, and each row is multiplied by the key A.

  1. Number the message: space = 0, A = 1, B = 2, …, Z = 26.
  2. Group the numbers into 1 × n rows for an n × n key, padding the last row with spaces (0).
  3. Encode: each uncoded row X becomes the coded row Y = XA.
  4. Decode: the receiver multiplies by the inverse, YA⁻¹ = XAA⁻¹ = X, and reads the numbers back as letters.

Worked example

Larson's MEET ME MONDAY, with A = [1 −2 2; −1 1 3; 1 −1 −4]

  1. 1M E E T _ M E _ M O N D A Y _ → [13 5 5] [20 0 13] [5 0 13] [15 14 4] [1 25 0] (the last space pads the row).
  2. 2[13 5 5]A = [13 − 5 + 5 −26 + 5 − 5 26 + 15 − 20] = [13 −26 21]. The rest encode to [33 −53 −12] [18 −23 −42] [5 −20 56] [−24 23 77].
  3. 3To decode, A⁻¹ = [−1 −10 −8; −1 −6 −5; 0 −1 −1], and [13 −26 21]A⁻¹ = [13 5 5] = M E E.

The key has to be invertible: decoding is multiplication by A⁻¹. A singular key would send different messages to the same coded rows, and nobody could decode them.

Check yourself

Answer these out loud, without scrolling up. Any you can't, reread that section — then let the drill mark you.

  1. 1.What two products must equal I for B to be the inverse of A, and why can't a 2 × 3 matrix have an inverse?
  2. 2.Write the inverse of [a b; c d] and say when it fails to exist.
  3. 3.You row-reduce [A | I]. What do you see if A is singular, and what do you read off if it isn't?
  4. 4.What are (AB)⁻¹, (cA)⁻¹ and (Aᵀ)⁻¹ in terms of A⁻¹ and B⁻¹?
  5. 5.A is invertible. Write the solution of Ax = b, and the only solution of Ax = 0.
  6. 6.In the Hill cipher with key A, how is a row encoded and how is it decoded?