4.3 Rank inequalities and the transpose

Rank–nullity measures one matrix at a time. This section compares the ranks of matrices built from one another. Multiplying by an invertible matrix does not change the rank, and multiplying by an arbitrary matrix can only lower it:

rank (𝐴 𝐵) \leq min (rank 𝐴, rank 𝐵) .

We prove this in three ways, by comparing images, by comparing kernels, and by restricting $𝐴$ to the image of $𝐵$ , and the last proof says exactly how much rank is lost. The transpose $𝐴^{𝖳}$ has the same rank as $𝐴$ , although its columns are the rows of $𝐴$ and live in a different space. This equality, row rank equals column rank, is the main theorem of the section. It completes the count of dimensions of the four subspaces attached to a matrix. Finally, matrices of rank one are exactly the products $𝐮 𝐯^{𝖳}$ , rank is subadditive, and the column–row factorization $𝐴 = 𝐶 𝑅$ writes a matrix of rank $𝑟$ as a sum of $𝑟$ matrices of rank one, which is the fewest possible.

Throughout, $𝐹$ is a field. For $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ we write $im 𝐴 = im 𝑇_{𝐴} \subseteq 𝐹^{𝑚}$ and $ker 𝐴 =$ $ker 𝑇_{𝐴} \subseteq$ $𝐹^{𝑛}$ for the column space and the null space (Definition 2.6.17). So $rank 𝐴 = dim im 𝐴$ (Theorem 4.2.7) and $dim ker 𝐴 =$ $𝑛 -$ $rank 𝐴$ (Theorem 4.2.11).

4.3.1Invertible factors

We already know that $rank (𝐺 𝐴) = rank 𝐴$ for invertible $𝐺$ , because $rref (𝐺 𝐴) =$ $rref (𝐴)$ (Proposition 3.5.2(c)), and that $rank (𝐴 𝐻) = rank 𝐴$ for invertible $𝐻$ , from the uniqueness of the rank normal form (Exercise 3.5.41(c)). The second proof was roundabout, because row reduction cannot see column operations. Now that rank is a dimension, both statements have short proofs. They are also the reason the rank of a linear map can be read off any of its matrices: changing bases multiplies ${[𝑇]}_{𝒞︀ ℬ︀}$ on the left and on the right by invertible matrices (Section 4.5), and that cannot change the rank.

Intuition (Outputs and inputs). In $𝐺 𝐴$ the matrix $𝐺$ acts after $𝐴$ , on the outputs $𝐴 𝐱$ . An invertible $𝐺$ is injective, so it never sends a nonzero output to $𝟎$ : $𝐺 𝐴 𝐱 = 𝟎$ only when $𝐴 𝐱 = 𝟎$ , and $ker (𝐺 𝐴) = ker 𝐴$ . But $𝐺$ moves the outputs, so $im (𝐺 𝐴)$ , the set of vectors $𝐺 𝐲$ with $𝐲 \in im 𝐴$ , is in general a different subspace of $𝐹^{𝑚}$ . It has the same dimension, since an injective map preserves dimension.

In $𝐴 𝐻$ the matrix $𝐻$ acts before $𝐴$ , on the inputs. An invertible $𝐻$ is surjective, so $𝐴 𝐻$ still sees every input, and $im (𝐴 𝐻) = im 𝐴$ . But the kernel moves: $𝐴 𝐻 𝐱 = 𝟎$ exactly when $𝐻 𝐱 \in ker 𝐴$ . So each of $𝐺 𝐴$ and $𝐴 𝐻$ keeps one of the two subspaces and moves the other by an invertible map.

Proposition 4.3.1 (Invertible factors preserve rank). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

, and let

𝐺 \in 𝐹^{𝑚 \times 𝑚}

and

𝐻 \in 𝐹^{𝑛 \times 𝑛}

be invertible.

(a) $ker (𝐺 𝐴) = ker 𝐴$ , and $rank (𝐺 𝐴) = rank 𝐴$ .
(b) $im (𝐴 𝐻) = im 𝐴$ , and $rank (𝐴 𝐻) = rank 𝐴$ .

In particular,

rank (𝐺 𝐴 𝐻) =

rank 𝐴

The first proof is the lecture’s. It compares images, using the restriction identity $im (𝑇 𝑆) =$ $im (𝑇 ↾_{im 𝑆})$ .

Proof (by restriction, comparing images).routine

Uses. Theorem 2.4.2 (The matrix of a composite), Proposition 2.5.4 (Left inverses give uniqueness), Proposition 2.5.5 (Right inverses give existence), Proposition 4.2.3 (Properties of restriction), Proposition 4.2.6 (Injective maps preserve dimension), Proposition 2.6.15 (Kernels and images of composites), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ )

Techniques. Restrict to a subspace (Technique 4.2.5)

Hint 1. Write

𝑇_{𝐺 𝐴} = 𝑇_{𝐺} \circ 𝑇_{𝐴}

. By Proposition 4.2.3(b),

im (𝐺 𝐴)

is the image of

𝑇_{𝐺}

restricted to

im 𝐴

. What do you know about

𝑇_{𝐺}

Hint 2.

𝑇_{𝐺}

is injective, so its restriction to

im 𝐴

is an injective linear map onto

im (𝐺 𝐴)

. For

𝐴 𝐻

, what is

im 𝑇_{𝐻}

Sketch.

im (𝐺 𝐴) =

im (𝑇_{𝐺} ↾_{im 𝐴})

, and

𝑇_{𝐺}

is injective because

𝑇_{𝐺^{- 1}}

is a left inverse, so the restriction carries

im 𝐴

injectively onto

im (𝐺 𝐴)

and the dimensions agree. On the other side,

im (𝐴 𝐻) =

im (𝑇_{𝐴} ↾_{im 𝐻}) =

im (𝑇_{𝐴} ↾_{𝐹^{𝑛}}) =

im 𝐴

, because

𝑇_{𝐻}

is surjective. The kernel statement in (a) is Proposition 2.6.15(a).

By Theorem 2.4.2, $𝑇_{𝐺 𝐴} = 𝑇_{𝐺} \circ 𝑇_{𝐴}$ and $𝑇_{𝐴 𝐻} = 𝑇_{𝐴} \circ 𝑇_{𝐻}$ . Since $𝐺^{- 1} 𝐺 = 𝐼_{𝑚}$ and $𝐻 𝐻^{- 1} = 𝐼_{𝑛}$ , the map $𝑇_{𝐺}$ is injective (Proposition 2.5.4) and $𝑇_{𝐻}$ is surjective (Proposition 2.5.5).

(a) By Proposition 4.2.3(b), $im (𝐺 𝐴) =$ $im (𝑇_{𝐺} ↾_{im 𝐴})$ . The restriction $𝑇_{𝐺} ↾_{im 𝐴}$ is linear and injective (Proposition 4.2.3(a), (c)), so Proposition 4.2.6(a), applied to it, gives $dim im (𝐺 𝐴) =$ $dim im 𝐴$ . That is, $rank (𝐺 𝐴) = rank 𝐴$ (Theorem 4.2.7). Since $𝑇_{𝐺}$ is injective, $ker (𝐺 𝐴) = ker 𝐴$ by Proposition 2.6.15(a).

(b) By Proposition 4.2.3(b), $im (𝐴 𝐻) =$ $im (𝑇_{𝐴} ↾_{im 𝐻})$ . Since $im 𝐻 = 𝐹^{𝑛}$ , this restriction is $𝑇_{𝐴}$ itself, so $im (𝐴 𝐻) = im 𝐴$ , and in particular $rank (𝐴 𝐻) = rank 𝐴$ .

Finally, $rank (𝐺 𝐴 𝐻) =$ $rank (𝐺 (𝐴 𝐻)) =$ $rank (𝐴 𝐻) =$ $rank 𝐴$ by (a) and (b). □

The lecture remarks that the same statements follow from kernels and rank–nullity. Here is that proof.

Proof (by kernels and rank–nullity).routine

Uses. Proposition 2.6.15 (Kernels and images of composites), Theorem 4.2.11 (Rank–nullity), Proposition 4.2.3 (Properties of restriction), Proposition 4.2.6 (Injective maps preserve dimension), Proposition 4.1.21 (Dimensions of subspaces)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1.

𝐺 𝐴

and

𝐴 𝐻

have

𝑛

columns, as

𝐴

does. By rank–nullity it suffices to compare

dim ker (𝐺 𝐴)

and

dim ker (𝐴 𝐻)

with

dim ker 𝐴

Hint 2.

𝐺

can be cancelled from

𝐺 𝐴 𝐱 = 𝟎

. For

𝐴 𝐻

, show that

𝐱 \in ker (𝐴 𝐻)

if and only if

𝐻 𝐱 \in ker 𝐴

, and use

𝑇_{𝐻}

to move one kernel onto the other.

Sketch. If

𝐺 𝐴 𝐱 = 𝟎

, then

𝐴 𝐱 =

𝐺^{- 1} 𝐺 𝐴 𝐱 =

𝟎

, so

ker (𝐺 𝐴) = ker 𝐴

, and rank–nullity gives

rank (𝐺 𝐴) =

𝑛 -

dim ker 𝐴 =

rank 𝐴

. Next,

𝐱 \in ker (𝐴 𝐻)

if and only if

𝐻 𝐱 \in ker 𝐴

, so

𝑇_{𝐻}

restricts to an injective linear map from

ker (𝐴 𝐻)

onto

ker 𝐴

. The kernels have the same dimension, so

rank (𝐴 𝐻) = rank 𝐴

by rank–nullity, and then

im (𝐴 𝐻) \subseteq im 𝐴

with equal dimensions forces

im (𝐴 𝐻) = im 𝐴

(a) By Proposition 2.6.15(a), $ker 𝐴 \subseteq ker (𝐺 𝐴)$ . Conversely, if $𝐺 𝐴 𝐱 = 𝟎$ , then $𝐴 𝐱 =$ $𝐺^{- 1} (𝐺 𝐴 𝐱) =$ $𝟎$ . So $ker (𝐺 𝐴) = ker 𝐴$ . The matrices $𝐺 𝐴$ and $𝐴$ both have $𝑛$ columns, so by Theorem 4.2.11(a),

rank (𝐺 𝐴) = 𝑛 - dim ker (𝐺 𝐴) = 𝑛 - dim ker 𝐴 = rank 𝐴 .

(b) For $𝐱 \in 𝐹^{𝑛}$ , we have $𝐴 𝐻 𝐱 = 𝟎$ if and only if $𝐻 𝐱 \in ker 𝐴$ . So $𝑇_{𝐻}$ maps $ker (𝐴 𝐻)$ into $ker 𝐴$ . Since $𝐻^{- 1} 𝐻 = 𝐼_{𝑛}$ , $𝑇_{𝐻}$ is injective, so its restriction to $ker (𝐴 𝐻)$ is linear and injective (Proposition 4.2.3). It maps onto $ker 𝐴$ : if $𝐲 \in ker 𝐴$ , then $𝐱 = 𝐻^{- 1} 𝐲$ satisfies $𝐴 𝐻 𝐱 = 𝐴 𝐲 = 𝟎$ and $𝐻 𝐱 = 𝐲$ . By Proposition 4.2.6(a), $dim ker (𝐴 𝐻) =$ $dim ker 𝐴$ , and since $𝐴 𝐻$ has $𝑛$ columns, Theorem 4.2.11(a) gives

rank (𝐴 𝐻) = 𝑛 - dim ker (𝐴 𝐻) = 𝑛 - dim ker 𝐴 = rank 𝐴 .

Finally, $im (𝐴 𝐻) \subseteq im 𝐴$ by Proposition 2.6.15(b), and these subspaces of $𝐹^{𝑚}$ have the same dimension, so they are equal (Proposition 4.1.21(b)).

As in the first proof, $rank (𝐺 𝐴 𝐻) =$ $rank 𝐴$ follows from (a) and (b). □

The two proofs split the work in opposite ways. In the first, the left factor needs an argument (an injective map preserves dimension) and the right factor is free (a surjective map on the inputs changes nothing). In the second, the left factor is free (the kernel does not change) and the right factor needs the argument. The same split reappears in Section 4.3.2, where an arbitrary product is compared with its factors.

By Exercise 3.5.41(d), two matrices $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ satisfy $𝐵 = 𝐺 𝐴 𝐻$ for some invertible $𝐺$ and $𝐻$ if and only if they have the same rank. So the rank is the only information about $𝐴$ that row and column operations together preserve. In particular, similar matrices $𝐵 = 𝑃 𝐴 𝑃^{- 1}$ have the same rank, a fact we return to in Section 4.5.

Exercise 4.3.2.routine Let

𝐴 = (\begin{matrix} 1 & 2 \\ 2 & 4 \end{matrix})

𝐺 = (\begin{matrix} 1 & 0 \\ - 2 & 1 \end{matrix})

, and

𝐻 = (\begin{matrix} 1 & - 2 \\ 0 & 1 \end{matrix})

, over

ℚ

. Compute

𝐺 𝐴

and

𝐴 𝐻

, and find the kernel and the image of each of

𝐴

𝐺 𝐴

, and

𝐴 𝐻

. Which subspaces agree, and which do not?

Solution.

Uses. Proposition 4.3.1 (Invertible factors preserve rank), Proposition 2.6.18 (The column space is spanned by the columns)

Hint 1.

𝐺

adds

- 2

times row

1

to row

2

, and

𝐻

adds

- 2

times column

1

to column

2

Hint 2. All three matrices have rank

1

, so each kernel and each image is a line. Find a spanning vector for each.

Sketch.

𝐺 𝐴 = (\begin{matrix} 1 & 2 \\ 0 & 0 \end{matrix})

and

𝐴 𝐻 = (\begin{matrix} 1 & 0 \\ 2 & 0 \end{matrix})

. The kernels are

span ((- 2, 1))

span ((- 2, 1))

span (𝐞_{2})

, and the images are

span ((1, 2))

span (𝐞_{1})

span ((1, 2))

, for

𝐴

𝐺 𝐴

𝐴 𝐻

respectively. So

𝐺 𝐴

keeps the kernel of

𝐴

and moves the image, and

𝐴 𝐻

keeps the image and moves the kernel.

Multiplying out,

\begin{aligned} 𝐺 𝐴 & = (\begin{matrix} 1 & 2 \\ 2 - 4 & 4 - 8 \end{matrix}) = (\begin{matrix} 1 & 2 \\ 0 & 0 \end{matrix}), \\ 𝐴 𝐻 & = (\begin{matrix} 1 & - 2 + 2 \\ 2 & - 4 + 4 \end{matrix}) = (\begin{matrix} 1 & 0 \\ 2 & 0 \end{matrix}) . \end{aligned}

The columns of $𝐴$ are $(1, 2)$ and $2 (1, 2)$ , so $im 𝐴 = span ((1, 2))$ (Proposition 2.6.18), and $𝐴 𝐱 = 𝟎$ means $𝑥_{1} + 2 𝑥_{2} = 0$ , so $ker 𝐴 =$ $span ((- 2, 1))$ . For $𝐺 𝐴$ , the columns are $𝐞_{1}$ and $2 𝐞_{1}$ , so $im (𝐺 𝐴) =$ $span (𝐞_{1})$ , and $𝐺 𝐴 𝐱 = 𝟎$ again means $𝑥_{1} + 2 𝑥_{2} = 0$ , so $ker (𝐺 𝐴) =$ $span ((- 2, 1))$ . For $𝐴 𝐻$ , the columns are $(1, 2)$ and $𝟎$ , so $im (𝐴 𝐻) =$ $span ((1, 2))$ , and $𝐴 𝐻 𝐱 = 𝑥_{1} (1, 2)$ vanishes exactly when $𝑥_{1} = 0$ , so $ker (𝐴 𝐻) =$ $span (𝐞_{2})$ .

So $ker (𝐺 𝐴) = ker 𝐴$ but $im (𝐺 𝐴) \neq im 𝐴$ , and $im (𝐴 𝐻) = im 𝐴$ but $ker (𝐴 𝐻) \neq ker 𝐴$ , as Proposition 4.3.1 and Intuition (Outputs and inputs) predict. All three matrices have rank $1$ . Note that $ker (𝐴 𝐻) =$ $𝐻^{- 1} (ker 𝐴)$ : indeed $𝐻^{- 1} = (\begin{matrix} 1 & 2 \\ 0 & 1 \end{matrix})$ and $𝐻^{- 1} (- 2, 1) = (0, 1)$ .

4.3.2The rank of a product

Intuition (A pipeline is no wider than its narrowest stage). For $𝐱 \in 𝐹^{𝑝}$ , $𝐴 𝐵 𝐱 = 𝐴 (𝐵 𝐱)$ : first $𝐵$ , then $𝐴$ . Every output of $𝐴 𝐵$ is an output of $𝐴$ , so $im (𝐴 𝐵) \subseteq im 𝐴$ ; the product cannot reach a direction that $𝐴$ cannot reach. On the other hand, $𝐴$ only ever receives the vectors $𝐵 𝐱$ , which fill a space of dimension $rank 𝐵$ , and a linear map does not raise dimension. So

rank (𝐴 𝐵) \leq rank 𝐴 and rank (𝐴 𝐵) \leq rank 𝐵 .

The first bound is about where the outputs land and is immediate. The second is about how many independent directions enter $𝐴$ , and it needs a dimension argument.

Theorem 4.3.3 (Rank of a product).

(a)Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ . Then $im (𝐴 𝐵) \subseteq im 𝐴$ and $ker 𝐵 \subseteq ker (𝐴 𝐵)$ , and
$rank (𝐴 𝐵) \leq min (rank 𝐴, rank 𝐵) .$
(b)More generally, let $𝑈$ and $𝑉$ be finite-dimensional, and let $𝑆 \in L (𝑈, 𝑉)$ and $𝑇 \in L (𝑉, 𝑊)$ . Then
$rank (𝑇 𝑆) \leq min (rank 𝑇, rank 𝑆) .$

Part (a) is part (b) for $𝑆 = 𝑇_{𝐵}$ and $𝑇 = 𝑇_{𝐴}$ , since $𝑇_{𝐴 𝐵} = 𝑇_{𝐴} \circ 𝑇_{𝐵}$ (Theorem 2.4.2) and $rank 𝐴 = rank 𝑇_{𝐴}$ (Definition 4.2.14); the two containments in (a) are Proposition 2.6.15. So we prove (b). In both proofs below, the bound by $rank 𝑇$ comes from $im (𝑇 𝑆) \subseteq im 𝑇$ . They differ in how they prove the bound by $rank 𝑆$ .

Proof (comparing images).routine

Uses. Proposition 2.6.15 (Kernels and images of composites), Theorem 4.2.11 (Rank–nullity), Proposition 4.1.21 (Dimensions of subspaces), Proposition 4.2.3 (Properties of restriction), Proposition 2.1.16 (Linear maps preserve spans and linear relations), Corollary 4.1.11 (Spanning lists are long)

Techniques. Restrict to a subspace (Technique 4.2.5)

Hint 1.

im (𝑇 𝑆) \subseteq im 𝑇

, which gives one inequality at once.

Hint 2. For the other,

im (𝑇 𝑆) =

im (𝑇 ↾_{im 𝑆})

consists of the values of

𝑇

im 𝑆

. Take a basis of

im 𝑆

and push it forward with

𝑇

Hint 3. A space spanned by

𝑟

vectors has dimension at most

𝑟

Sketch.

im (𝑇 𝑆) \subseteq im 𝑇

gives

rank (𝑇 𝑆) \leq rank 𝑇

. If

𝐬_{1}, \dots, 𝐬_{𝑟}

is a basis of

im 𝑆

, then

im (𝑇 𝑆) =

im (𝑇 ↾_{im 𝑆})

is spanned by

𝑇 (𝐬_{1}),

\dots,

𝑇 (𝐬_{𝑟})

, so its dimension is at most

𝑟 = rank 𝑆

Since $𝑈$ and $𝑉$ are finite-dimensional, $im 𝑆$ , $im 𝑇$ , and $im (𝑇 𝑆)$ are finite-dimensional (Theorem 4.2.11(b)), so all three ranks are defined.

The bound by $rank 𝑇$ . By Proposition 2.6.15(b), $im (𝑇 𝑆) \subseteq im 𝑇$ , so $rank (𝑇 𝑆) \leq rank 𝑇$ by Proposition 4.1.21(a).

The bound by $rank 𝑆$ . Let $𝑟 = rank 𝑆$ and let $𝐬_{1}, \dots, 𝐬_{𝑟}$ be a basis of $im 𝑆$ (the empty list if $𝑟 = 0$ ). By Proposition 4.2.3(b) and Proposition 2.1.16(a),

im (𝑇 𝑆) = im (𝑇 ↾_{im 𝑆}) = span (𝑇 (𝐬_{1}), \dots, 𝑇 (𝐬_{𝑟})) .

So $im (𝑇 𝑆)$ is spanned by a list of length $𝑟$ , and $dim im (𝑇 𝑆) \leq 𝑟$ by Corollary 4.1.11(a). That is, $rank (𝑇 𝑆) \leq rank 𝑆$ . □

The second proof moves the comparison to the domain $𝑈$ , where $𝑆$ and $𝑇 𝑆$ have a common domain and rank–nullity applies to both.

Proof (comparing kernels, with rank–nullity).routine

Uses. Proposition 2.6.15 (Kernels and images of composites), Proposition 4.1.21 (Dimensions of subspaces), Theorem 4.2.11 (Rank–nullity)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. The bound by

rank 𝑇

is the image comparison

im (𝑇 𝑆) \subseteq im 𝑇

. For the bound by

rank 𝑆

, compare kernels instead: which of

ker 𝑆

and

ker (𝑇 𝑆)

contains the other?

Hint 2.

ker 𝑆 \subseteq ker (𝑇 𝑆)

, both subspaces of

𝑈

. Apply rank–nullity to

𝑆

and to

𝑇 𝑆

Sketch.

rank (𝑇 𝑆) \leq rank 𝑇

because

im (𝑇 𝑆) \subseteq im 𝑇

. Since

ker 𝑆 \subseteq ker (𝑇 𝑆)

, rank–nullity on

𝑈

gives

rank (𝑇 𝑆) =

dim 𝑈 -

dim ker (𝑇 𝑆) \leq

dim 𝑈 -

dim ker 𝑆 =

rank 𝑆

As in the first proof, $im (𝑇 𝑆) \subseteq im 𝑇$ (Proposition 2.6.15(b)), so $rank (𝑇 𝑆) \leq rank 𝑇$ (Proposition 4.1.21(a)).

By Proposition 2.6.15(a), $ker 𝑆 \subseteq ker (𝑇 𝑆)$ . Both are subspaces of the finite-dimensional space $𝑈$ , so $dim ker 𝑆 \leq$ $dim ker (𝑇 𝑆)$ (Proposition 4.1.21(a)). By Theorem 4.2.11(b), applied to $𝑆$ and to $𝑇 𝑆$ , which are both defined on $𝑈$ ,

\begin{aligned} rank (𝑇 𝑆) & = dim 𝑈 - dim ker (𝑇 𝑆) \\ \leq dim 𝑈 - dim ker 𝑆 = rank 𝑆, \end{aligned}

as desired. □

Both inequalities can be strict, even at the same time.

Example 4.3.4 (A product of rank zero). Let

𝑁 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})

, so

𝑁 𝐞_{1} = 𝟎

and

𝑁 𝐞_{2} = 𝐞_{1}

. Then

rank 𝑁 = 1

, but

𝑁^{2} = 0

has rank

0 <

min (rank 𝑁, rank 𝑁)

. In

𝑁 𝑁

, the left factor kills exactly what the right factor produces:

im 𝑁 =

span (𝐞_{1}) =

ker 𝑁

. The order of the factors matters too: with

𝑀 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})

𝑀 𝑁 = 𝑁

has rank

1

but

𝑁 𝑀 = 0

, so

rank (𝐴 𝐵)

and

rank (𝐵 𝐴)

can differ even for square matrices.

What a product loses

The example shows where the rank goes. $𝐴 𝐵$ applies $𝐴$ to the vectors of $im 𝐵$ , and $𝐴$ kills those that lie in $ker 𝐴$ . Restricting $𝐴$ to $im 𝐵$ makes this exact. This is the lecture’s restriction view of a composite, and it gives the third proof of the bound by $rank 𝐵$ .

Proposition 4.3.5 (Rank of a product, exactly). Let $𝑆 \in L (𝑈, 𝑉)$ and $𝑇 \in L (𝑉, 𝑊)$ , with $𝑈$ finite-dimensional.

(a) $rank (𝑇 𝑆) =$ $rank 𝑆 -$ $dim (im 𝑆 \cap ker 𝑇)$ .
(b) $rank (𝑇 𝑆) = rank 𝑆$ if and only if $im 𝑆 \cap ker 𝑇 = {𝟎}$ . If $𝑉$ is also finite-dimensional, then $rank (𝑇 𝑆) = rank 𝑇$ if and only if $im 𝑆 + ker 𝑇 = 𝑉$ .

For matrices $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ , (a) reads

rank (𝐴 𝐵) = rank 𝐵 - dim (im 𝐵 \cap ker 𝐴) .

(4.3.1)

Proof (by restriction).standard

Uses. Theorem 4.2.11 (Rank–nullity), Proposition 4.2.3 (Properties of restriction), Exercise 4.2.44, Proposition 2.6.15 (Kernels and images of composites), Proposition 4.1.21 (Dimensions of subspaces), Exercise 2.6.39, Theorem 2.4.2 (The matrix of a composite)

Techniques. Restrict to a subspace (Technique 4.2.5), Dimension counting (Technique 4.2.24)

Hint 1.

im (𝑇 𝑆) =

im (𝑇 ↾_{im 𝑆})

. What is the kernel of

𝑇 ↾_{im 𝑆}

Hint 2. Apply rank–nullity to

𝑇 ↾_{im 𝑆}

, whose domain is the finite-dimensional space

im 𝑆

Hint 3. For the last statement,

im (𝑇 𝑆) \subseteq im 𝑇

; when do two finite-dimensional nested subspaces have the same dimension? Then use Exercise 2.6.39(b).

Sketch. The restriction

𝑅 = 𝑇 ↾_{im 𝑆}

has domain

im 𝑆

, of dimension

rank 𝑆

, kernel

im 𝑆 \cap ker 𝑇

, and image

im (𝑇 𝑆)

. Rank–nullity for

𝑅

is (a), and (a) gives the first half of (b). For the second half,

im (𝑇 𝑆) \subseteq im 𝑇

, so the ranks agree exactly when the images agree, which by Exercise 2.6.39(b) means

im 𝑆 + ker 𝑇 = 𝑉

(a) Since $𝑈$ is finite-dimensional, so is $im 𝑆$ , and $dim im 𝑆 = rank 𝑆$ (Theorem 4.2.11(b)). Let $𝑅 =$ $𝑇 ↾_{im 𝑆} : im 𝑆 \to$ $𝑊$ . By Proposition 4.2.3, $𝑅$ is linear, $ker 𝑅 = im 𝑆 \cap ker 𝑇$ , and $im 𝑅 = im (𝑇 𝑆)$ . Rank–nullity for $𝑅$ (Theorem 4.2.11(b)) gives

rank 𝑆 = dim im 𝑆 = dim (im 𝑆 \cap ker 𝑇) + dim im (𝑇 𝑆),

which is (a). (This is Exercise 4.2.44(a) for the subspace $im 𝑆$ .)

(b) By (a), $rank (𝑇 𝑆) = rank 𝑆$ if and only if $dim (im 𝑆 \cap ker 𝑇) = 0$ , that is, $im 𝑆 \cap ker 𝑇 = {𝟎}$ . Now let $𝑉$ be finite-dimensional, so that $im 𝑇$ is finite-dimensional. Since $im (𝑇 𝑆) \subseteq im 𝑇$ (Proposition 2.6.15(b)), Proposition 4.1.21(b) shows that $rank (𝑇 𝑆) = rank 𝑇$ if and only if $im (𝑇 𝑆) = im 𝑇$ , and by Exercise 2.6.39(b) this holds if and only if $im 𝑆 + ker 𝑇 = 𝑉$ .

The matrix statement is (a) for $𝑆 = 𝑇_{𝐵}$ and $𝑇 = 𝑇_{𝐴}$ (Theorem 2.4.2). □

Intuition (Three proofs of

rank (𝑇 𝑆) \leq rank 𝑆

). The image proof works in the middle space

𝑉

: it pushes a basis of

im 𝑆

forward with

𝑇

and observes that at most

rank 𝑆

vectors come out. The kernel proof works in the domain

𝑈

: whatever

𝑆

kills,

𝑇 𝑆

kills too, and rank–nullity converts a larger kernel into a smaller image. The restriction proof is the sharpest, because it computes the loss instead of bounding it:

𝑇 𝑆

loses exactly the directions that

𝑆

produces and

𝑇

destroys,

im 𝑆 \cap ker 𝑇

. It answers the question of when the inequality is an equality, and it also gives lower bounds for

rank (𝑇 𝑆)

, which are the subject of Exercise 4.3.30 and Exercise 4.3.31. When all you need is the inequality, the image proof is the one to remember.

Example 4.3.6 (Powers of a square matrix). Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . By (4.3.1) with $𝐵 = 𝐴$ ,

rank (𝐴^{2}) = rank 𝐴 - dim (im 𝐴 \cap ker 𝐴) .

So $rank (𝐴^{2}) = rank 𝐴$ if and only if $im 𝐴 \cap ker 𝐴 = {𝟎}$ . For the projection $𝑃 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ , $im 𝑃 = span (𝐞_{1})$ and $ker 𝑃 = span (𝐞_{2})$ meet only in $𝟎$ , and indeed $𝑃^{2} = 𝑃$ . For $𝑁$ of Example 4.3.4, $im 𝑁 = ker 𝑁$ , and $rank (𝑁^{2}) = 1 - 1 = 0$ .

With $𝐵 = 𝐴^{𝑘}$ instead, the formula gives $rank (𝐴^{𝑘 + 1}) =$ $rank (𝐴^{𝑘}) -$ $dim (im 𝐴^{𝑘} \cap ker 𝐴)$ . The subspaces $im 𝐴^{𝑘}$ shrink as $𝑘$ grows, so the drops $rank (𝐴^{𝑘}) -$ $rank (𝐴^{𝑘 + 1})$ can only decrease. This is Exercise 4.2.52 in the language of images, and by Exercise 4.2.51 the ranks stop decreasing by $𝑘 = 𝑛$ .

Exercise 4.3.7.routine Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ with $𝑚 < 𝑛$ .

(a)Show that $𝐵 𝐴 \in 𝐹^{𝑛 \times 𝑛}$ is not invertible.
(b)Give an example with $𝐴 𝐵 = 𝐼_{𝑚}$ .
(c)Show that if $𝐴 𝐵 = 𝐼_{𝑚}$ , then $rank (𝐵 𝐴) = 𝑚$ .

Solution.

Uses. Theorem 4.3.3 (Rank of a product), Proposition 3.5.2 (First properties of rank), Corollary 3.5.25 (The invertible matrix theorem), Theorem 2.4.34 (Block multiplication)

Hint 1.

rank (𝐵 𝐴) \leq rank 𝐴

, and

𝐴

has only

𝑚

rows.

Hint 2. For (b), try block matrices built from

𝐼_{𝑚}

and zeros.

Hint 3. For (c), sandwich

𝐼_{𝑚} =

(𝐴 𝐵) (𝐴 𝐵) =

𝐴 (𝐵 𝐴) 𝐵

Sketch. (a)

rank (𝐵 𝐴) \leq

rank 𝐴 \leq

𝑚 <

𝑛

, so

𝐵 𝐴

is not invertible. (b)

𝐴 = (\begin{matrix} 𝐼_{𝑚} & 0 \end{matrix})

𝐵 = (\begin{matrix} 𝐼_{𝑚} \\ 0 \end{matrix})

. (c)

𝑚 =

rank (𝐼_{𝑚}) =

rank (𝐴 (𝐵 𝐴) 𝐵) \leq

rank (𝐵 𝐴) \leq

𝑚

(a) By Theorem 4.3.3 and Proposition 3.5.2(a), $rank (𝐵 𝐴) \leq$ $rank 𝐴 \leq$ $𝑚 <$ $𝑛$ . An invertible $𝑛 \times 𝑛$ matrix has rank $𝑛$ (Corollary 3.5.25), so $𝐵 𝐴$ is not invertible.

(b) Let $𝐴 =$ $(\begin{matrix} 𝐼_{𝑚} & 0 \end{matrix}) \in$ $𝐹^{𝑚 \times 𝑛}$ and $𝐵 =$ $(\begin{matrix} 𝐼_{𝑚} \\ 0 \end{matrix}) \in$ $𝐹^{𝑛 \times 𝑚}$ , where the zero blocks have $𝑛 - 𝑚$ columns and $𝑛 - 𝑚$ rows. By Theorem 2.4.34, $𝐴 𝐵 =$ $𝐼_{𝑚} 𝐼_{𝑚} +$ $0 \cdot$ $0 =$ $𝐼_{𝑚}$ . (Here $𝐵 𝐴 = (\begin{matrix} 𝐼_{𝑚} & 0 \\ 0 & 0 \end{matrix})$ , of rank $𝑚$ .)

(c) If $𝐴 𝐵 = 𝐼_{𝑚}$ , then $𝐼_{𝑚} =$ $(𝐴 𝐵) (𝐴 𝐵) =$ $𝐴 (𝐵 𝐴) 𝐵$ . By Theorem 4.3.3, applied twice,

𝑚 = rank (𝐼_{𝑚}) = rank (𝐴 (𝐵 𝐴) 𝐵) \leq rank (𝐵 𝐴) \leq 𝑚,

so $rank (𝐵 𝐴) = 𝑚$ .

4.3.3Row rank equals column rank

Intuition (Why this is surprising). Consider

𝐴 = (\begin{matrix} 1 & 2 & 1 & 4 \\ 2 & 4 & 0 & 6 \\ 1 & 2 & - 1 & 2 \end{matrix}) \in ℚ^{3 \times 4} .

Its four columns are vectors in $ℚ^{3}$ . They satisfy $𝐚_{2} = 2 𝐚_{1}$ and $𝐚_{4} = 3 𝐚_{1} + 𝐚_{3}$ , and $𝐚_{1}, 𝐚_{3}$ are independent, so exactly two of the columns are independent. Its three rows are vectors in $ℚ^{4}$ . They satisfy one relation, ${row}_{1} - {row}_{2} + {row}_{3} = 𝟎$ , and any two of them are independent, so again exactly two of the rows are independent.

Nothing in the definitions suggests that these two numbers should agree. The columns satisfy two independent relations and the rows only one; the columns live in $𝐹^{3}$ and the rows in $𝐹^{4}$ . For a $3 \times 100$ matrix, one count is about $100$ vectors in $𝐹^{3}$ and the other is about $3$ vectors in $𝐹^{100}$ . Yet the two counts always agree. Equivalently, the numbers of independent relations always differ by exactly the difference between the numbers of columns and rows: here $2 - 1 = 4 - 3$ .

The columns of $𝐴^{𝖳}$ are the rows of $𝐴$ , written as columns (Definition 2.4.21). So $im 𝐴^{𝖳} \subseteq 𝐹^{𝑛}$ is the span of the rows of $𝐴$ (Proposition 2.6.18), and $rank 𝐴^{𝖳}$ is its dimension.

Theorem 4.3.8 (Row rank equals column rank). For every $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ ,

rank 𝐴^{𝖳} = rank 𝐴 .

That is, the span of the rows of $𝐴$ , viewed as vectors in $𝐹^{𝑛}$ , has the same dimension as the span of its columns in $𝐹^{𝑚}$ .

The first proof reduces $𝐴$ to its rank normal form, where the statement is obvious.

Proof (via the rank normal form).routine

Uses. Theorem 3.5.27 (Rank normal form), Proposition 2.4.23 (Transpose of a product), Proposition 2.5.17 (Algebra of inverses), Proposition 4.3.1 (Invertible factors preserve rank), Proposition 2.6.18 (The column space is spanned by the columns), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ )

Techniques. Transpose to trade rows for columns (Technique 3.2.27)

Hint 1. The statement is obvious for

𝑁_{𝑘} = (\begin{matrix} 𝐼_{𝑘} & 0 \\ 0 & 0 \end{matrix})

. Reduce to it.

Hint 2. Transpose

𝐺 𝐴 𝐻 = 𝑁_{𝑘}

. Which factors of the result are invertible, and what is the rank of

𝑁_{𝑘}^{𝖳}

Sketch. With

𝐺 𝐴 𝐻 = 𝑁_{𝑘}

and

𝑘 = rank 𝐴

, transposing gives

𝐻^{𝖳} 𝐴^{𝖳} 𝐺^{𝖳} =

𝑁_{𝑘}^{𝖳}

, with

𝐻^{𝖳}

and

𝐺^{𝖳}

invertible. By Proposition 4.3.1,

rank 𝐴^{𝖳} =

rank 𝑁_{𝑘}^{𝖳}

, and

𝑁_{𝑘}^{𝖳}

has columns

𝐞_{1}, \dots, 𝐞_{𝑘}

followed by zero columns, so its rank is

𝑘

Let $𝑘 = rank 𝐴$ . By Theorem 3.5.27 there are invertible $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ and $𝐻 \in 𝐹^{𝑛 \times 𝑛}$ with $𝐺 𝐴 𝐻 = 𝑁_{𝑘}$ . Transposing with Proposition 2.4.23,

𝐻^{𝖳} 𝐴^{𝖳} 𝐺^{𝖳} = {(𝐺 𝐴 𝐻)}^{𝖳} = 𝑁_{𝑘}^{𝖳} .

The matrices $𝐻^{𝖳}$ and $𝐺^{𝖳}$ are invertible (Proposition 2.5.17(d)), so $rank 𝐴^{𝖳} =$ $rank (𝐻^{𝖳} 𝐴^{𝖳} 𝐺^{𝖳}) =$ $rank 𝑁_{𝑘}^{𝖳}$ by Proposition 4.3.1. The matrix $𝑁_{𝑘}^{𝖳} \in 𝐹^{𝑛 \times 𝑚}$ has $1$ in positions $(1, 1), \dots, (𝑘, 𝑘)$ and $0$ elsewhere, so its columns are $𝐞_{1}, \dots, 𝐞_{𝑘} \in 𝐹^{𝑛}$ followed by $𝑚 - 𝑘$ zero columns. Hence $im 𝑁_{𝑘}^{𝖳} =$ $span (𝐞_{1}, \dots, 𝐞_{𝑘})$ (Proposition 2.6.18), which has the basis $𝐞_{1}, \dots, 𝐞_{𝑘}$ . So $rank 𝑁_{𝑘}^{𝖳} = 𝑘$ (Theorem 4.2.7), and $rank 𝐴^{𝖳} =$ $𝑘 =$ $rank 𝐴$ . □

The second proof uses only row operations. They change the column space of $𝐴$ but keep its row space, and the reduced form exposes a basis of the row space.

Proof (row operations keep the row space, and RREF exposes it).standard

Uses. Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Proposition 2.4.23 (Transpose of a product), Proposition 2.5.17 (Algebra of inverses), Proposition 4.3.1 (Invertible factors preserve rank), Proposition 3.3.8 (Properties of the output), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Proposition 2.6.18 (The column space is spanned by the columns), Theorem 1.5.5 (Independence is decided at zero), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ )

Techniques. Reduce to RREF (Technique 3.3.22), Transpose to trade rows for columns (Technique 3.2.27)

Hint 1. Transpose

𝐺 𝐴 = 𝐴_{𝑟}

, and recall from Proposition 4.3.1(b) that an invertible factor on the right does not change the image.

Hint 2. So

𝐴

and

𝐴_{𝑟}

have the same row space. Which rows of

𝐴_{𝑟}

are nonzero, and why are they linearly independent?

Hint 3. Row

𝑠

𝐴_{𝑟}

has a

1

in the pivot column

𝑝_{𝑠}

, and every other row has a

0

there.

Sketch. From

𝐺 𝐴 = 𝐴_{𝑟}

we get

𝐴_{𝑟}^{𝖳} = 𝐴^{𝖳} 𝐺^{𝖳}

with

𝐺^{𝖳}

invertible, so

im 𝐴_{𝑟}^{𝖳} = im 𝐴^{𝖳}

by Proposition 4.3.1(b):

𝐴

and

𝐴_{𝑟}

have the same row space. The nonzero rows of

𝐴_{𝑟}

are its first

𝑘 = rank 𝐴

rows. They span its row space, and they are independent because row

𝑠

is the only one with a nonzero entry in column

𝑝_{𝑠}

. So the row space has dimension

𝑘

Let $𝑘 = rank 𝐴$ , and let $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ (Theorem 3.3.10). Transposing, $𝐴_{𝑟}^{𝖳} = 𝐴^{𝖳} 𝐺^{𝖳}$ (Proposition 2.4.23), and $𝐺^{𝖳}$ is invertible (Proposition 2.5.17(d)). By Proposition 4.3.1(b),

im 𝐴_{𝑟}^{𝖳} = im 𝐴^{𝖳} .

That is, $𝐴$ and $𝐴_{𝑟}$ have the same row space.

By Proposition 3.3.8(a), rows $𝑘 + 1, \dots, 𝑚$ of $𝐴_{𝑟}$ are zero. Let $𝛒_{1}, \dots, 𝛒_{𝑘} \in 𝐹^{𝑛}$ be the transposes of rows $1, \dots, 𝑘$ of $𝐴_{𝑟}$ . These are the first $𝑘$ columns of $𝐴_{𝑟}^{𝖳}$ , and its other columns are zero, so $im 𝐴_{𝑟}^{𝖳} =$ $span (𝛒_{1}, \dots, 𝛒_{𝑘})$ (Proposition 2.6.18). We show that $𝛒_{1}, \dots, 𝛒_{𝑘}$ is linearly independent. Let $𝑝_{1} < \dots < 𝑝_{𝑘}$ be the pivot columns of $𝐴_{𝑟}$ . Column $𝑝_{𝑡}$ of $𝐴_{𝑟}$ is $𝐞_{𝑡}$ (Lemma 3.3.16(b)), so entry $𝑝_{𝑡}$ of $𝛒_{𝑠}$ is $1$ if $𝑠 = 𝑡$ and $0$ if $𝑠 \neq 𝑡$ . Hence if $𝑐_{1} 𝛒_{1} +$ $\dots +$ $𝑐_{𝑘} 𝛒_{𝑘} =$ $𝟎$ , then entry $𝑝_{𝑡}$ of the left side is $𝑐_{𝑡}$ , so $𝑐_{𝑡} = 0$ for every $𝑡$ (Theorem 1.5.5).

So $𝛒_{1}, \dots, 𝛒_{𝑘}$ is a basis of $im 𝐴_{𝑟}^{𝖳} = im 𝐴^{𝖳}$ , and $rank 𝐴^{𝖳} =$ $dim im 𝐴^{𝖳} =$ $𝑘 =$ $rank 𝐴$ (Theorem 4.2.7). □

Both proofs reduce $𝐴$ to a form in which the theorem can be seen, but they teach different things. The first uses row and column operations together and lands on $𝑁_{𝑘}$ , whose transpose is again of the same shape. The second uses only row operations, and it rests on a contrast. Row operations change the column space but keep the relations among the columns (Corollary 3.2.17), hence the number of independent columns. They keep the row space itself. So reduction preserves both numbers, and in $𝐴_{𝑟}$ both are visibly the number of pivots. The second proof also computes something: the nonzero rows of $rref (𝐴)$ form a basis of the row space of $𝐴$ . A third proof, from the column–row factorization, is in Section 4.3.6, and for real matrices Exercise 4.3.33 gives a fourth. The transpose of a matrix is the matrix of the dual map, and the coordinate-free form of the theorem is that a linear map and its dual have the same rank (Section 13.1). That point of view is beyond the course.

Remark 4.3.9 (The two halves of the product inequality). With the transpose available, the two bounds in Theorem 4.3.3 are mirror images of each other (Technique 3.2.27). If we only knew the easy bound $rank (𝑋 𝑌) \leq rank 𝑋$ , which comes from $im (𝑋 𝑌) \subseteq im 𝑋$ , then

\begin{aligned} rank (𝐴 𝐵) & = rank ({(𝐴 𝐵)}^{𝖳}) = rank (𝐵^{𝖳} 𝐴^{𝖳}) \\ \leq rank 𝐵^{𝖳} = rank 𝐵 . \end{aligned}

So the bound that needed a dimension argument follows from the bound about images, once rows and columns are known to have the same rank.

The theorem adds a condition about rows to the Second Fundamental Theorem.

Corollary 4.3.10 (Independent rows). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. The following are equivalent.

(i)The rows of $𝐴$ are linearly independent.
(ii) $rank 𝐴 = 𝑚$ .
(iii)For every $𝐲 \in 𝐹^{𝑚}$ , the equation $𝐴 𝐱 = 𝐲$ has a solution.

In particular, a square matrix is invertible if and only if its rows are linearly independent.

Proof.routine

Uses. Theorem 4.3.8 (Row rank equals column rank), Theorem 3.5.12 (First Fundamental Theorem, completed), Theorem 3.5.13 (Second Fundamental Theorem, completed), Corollary 3.5.25 (The invertible matrix theorem)

Techniques. Transpose to trade rows for columns (Technique 3.2.27)

Hint. The rows of

𝐴

are the columns of

𝐴^{𝖳} \in 𝐹^{𝑛 \times 𝑚}

. Apply the First Fundamental Theorem to

𝐴^{𝖳}

Sketch. The rows of

𝐴

are independent iff the

𝑚

columns of

𝐴^{𝖳}

are, iff

rank 𝐴^{𝖳} = 𝑚

(Theorem 3.5.12 for

𝐴^{𝖳}

), iff

rank 𝐴 = 𝑚

, iff

𝑇_{𝐴}

is surjective (Theorem 3.5.13).

The rows of

𝐴

, written as columns, are the

𝑚

columns of

𝐴^{𝖳} \in 𝐹^{𝑛 \times 𝑚}

. By (III)

\Leftrightarrow

(VI) of Theorem 3.5.12 for

𝐴^{𝖳}

, they are linearly independent if and only if

rank 𝐴^{𝖳} = 𝑚

, that is,

rank 𝐴 = 𝑚

by Theorem 4.3.8. This proves (i)

\Leftrightarrow

(ii), and (ii)

\Leftrightarrow

(iii) is (VI)

\Leftrightarrow

(II) of Theorem 3.5.13. For

𝑚 = 𝑛

, condition (ii) says that

𝐴

is invertible (Corollary 3.5.25). □

Read as a statement about equations, (i) $\Leftrightarrow$ (iii) is natural in one direction. If some combination of the rows vanishes, say $𝑧_{1} (row 1) +$ $\dots +$ $𝑧_{𝑚} (row 𝑚) =$ $𝟎$ with not all $𝑧_{𝑖} = 0$ , then every solvable right side satisfies $𝑧_{1} 𝑦_{1} +$ $\dots +$ $𝑧_{𝑚} 𝑦_{𝑚} =$ $0$ , so not every $𝐲$ is reachable. The corollary says that this is the only obstruction.

Exercise 4.3.11.routine Over $𝔽_{5}$ , let $𝐴 = (\begin{matrix} 1 & 2 & 0 & 3 \\ 2 & 1 & 1 & 0 \\ 0 & 4 & 2 & 3 \end{matrix})$ .

(a)Find $rank 𝐴$ , and a basis of the row space of $𝐴$ from $rref (𝐴)$ .
(b)Find a basis of the row space consisting of rows of $𝐴$ , and express the remaining row in terms of it.

Solution.

Uses. Theorem 4.3.8 (Row rank equals column rank), Proposition 4.3.1 (Invertible factors preserve rank), Corollary 4.1.11 (Spanning lists are long)

Hint 1. Subtract twice row

1

from row

2

, then scale by

2^{- 1} = 3

Hint 2. For (b), the row space has dimension

rank 𝐴

. Are rows

1

and

2

multiples of each other?

Sketch.

rref (𝐴) =

(\begin{matrix} 1 & 0 & 4 & 4 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 0 & 0 \end{matrix})

, so

rank 𝐴 = 2

and

(1, 0, 4, 4),

(0, 1, 3, 2)

is a basis of the row space. Rows

1

and

2

are not proportional, so they are independent, and two independent vectors in a

2

-dimensional space form a basis. Row

3

is row

1

plus twice row

2

(a) Adding $- 2$ times row $1$ to row $2$ gives $(0, 1 - 4, 1, - 6) =$ $(0, 2, 1, 4)$ in $𝔽_{5}$ , and scaling by $2^{- 1} = 3$ gives $(0, 6, 3, 12) =$ $(0, 1, 3, 2)$ . Adding $- 4$ times this row to row $3$ gives $(0, 0, 2 - 12, 3 - 8) =$ $(0, 0, 0, 0)$ , and adding $- 2$ times it to row $1$ gives $(1, 0, - 6, - 1) =$ $(1, 0, 4, 4)$ . So

rref (𝐴) = (\begin{matrix} 1 & 0 & 4 & 4 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 0 & 0 \end{matrix}),

$rank 𝐴 = 2$ , and by the second proof of Theorem 4.3.8 the nonzero rows $(1, 0, 4, 4)$ and $(0, 1, 3, 2)$ form a basis of the row space of $𝐴$ .

(b) The row space has dimension $2$ . Rows $1$ and $2$ of $𝐴$ are not proportional (a multiple $𝑐 (1, 2, 0, 3)$ with third entry $1$ does not exist), so they are linearly independent, and two independent vectors in a $2$ -dimensional space form a basis. Row $3$ must be a combination of them, say row $3 = 𝑎$ (row $1$ ) $+ 𝑏$ (row $2$ ). The first entries give $0 = 𝑎 + 2 𝑏$ and the second entries $4 = 2 𝑎 + 𝑏$ ; so $𝑎 = - 2 𝑏 = 3 𝑏$ and $4 = 7 𝑏 = 2 𝑏$ in $𝔽_{5}$ , giving $𝑏 = 2$ and $𝑎 = 1$ . Indeed $(1, 2, 0, 3) +$ $2 (2, 1, 1, 0) =$ $(5, 4, 2, 3) =$ $(0, 4, 2, 3)$ in $𝔽_{5}$ .

4.3.4The four fundamental subspaces

A matrix $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ has a kernel and an image, and so does its transpose. Together they are the four subspaces attached to $𝐴$ .

Definition 4.3.12 (The four fundamental subspaces). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ . The four fundamental subspaces of $𝐴$ are

the column space $im 𝐴 \subseteq 𝐹^{𝑚}$ , the span of the columns of $𝐴$ ;
the null space $ker 𝐴 \subseteq 𝐹^{𝑛}$ ;
the row space $im 𝐴^{𝖳} \subseteq 𝐹^{𝑛}$ , the span of the rows of $𝐴$ written as columns;
the left null space $ker 𝐴^{𝖳} \subseteq 𝐹^{𝑚}$ .

The column rank of $𝐴$ is $dim im 𝐴$ , and the row rank is $dim im 𝐴^{𝖳}$ .

So Theorem 4.3.8 says that the row rank equals the column rank, and both equal $rank 𝐴$ . Table 4.3.1 summarizes the dimensions and bases found below. The name “left null space” comes from writing the condition on the left: since ${(𝐴^{𝖳} 𝐲)}^{𝖳} = 𝐲^{𝖳} 𝐴$ (Proposition 2.4.23), a vector $𝐲 \in 𝐹^{𝑚}$ lies in $ker 𝐴^{𝖳}$ exactly when $𝐲^{𝖳} 𝐴 = 𝟎^{𝖳}$ , that is,

𝑦_{1} (row 1 of 𝐴) + \dots + 𝑦_{𝑚} (row 𝑚 of 𝐴) = 𝟎 .

So the null space records the linear relations among the columns of $𝐴$ , and the left null space records the linear relations among the rows, or equivalently among the equations of the system $𝐴 𝐱 = 𝐲$ .

Proposition 4.3.13 (Dimensions of the four subspaces). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

have rank

𝑟

, and let

𝐺 \in 𝐹^{𝑚 \times 𝑚}

be invertible with

𝐺 𝐴 = 𝐴_{𝑟}

(a) $dim im 𝐴 = 𝑟$ , $dim ker 𝐴 = 𝑛 - 𝑟$ , $dim im 𝐴^{𝖳} = 𝑟$ , and $dim ker 𝐴^{𝖳} = 𝑚 - 𝑟$ .
(b)The pivot columns of $𝐴$ form a basis of $im 𝐴$ ; the basic solutions form a basis of $ker 𝐴$ ; the nonzero rows of $𝐴_{𝑟}$ , written as columns, form a basis of $im 𝐴^{𝖳}$ ; and the last $𝑚 - 𝑟$ rows of $𝐺$ , written as columns, form a basis of $ker 𝐴^{𝖳}$ .

Proof.routine

Uses. Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ), Theorem 4.2.11 (Rank–nullity), Theorem 4.3.8 (Row rank equals column rank), Remark 3.4.11 (A basis of the kernel), Exercise 3.3.57, Corollary 4.1.11 (Spanning lists are long)

Hint 1. Rank–nullity for

𝐴

gives two of the dimensions. Rank–nullity for

𝐴^{𝖳} \in 𝐹^{𝑛 \times 𝑚}

, together with Theorem 4.3.8, gives the other two.

Hint 2. For the basis of

ker 𝐴^{𝖳}

, Exercise 3.3.57 shows that the last

𝑚 - 𝑟

rows of

𝐺

span the relations among the rows of

𝐴

. How many of them are there?

Sketch. (a)

dim im 𝐴 = 𝑟

and

dim ker 𝐴 = 𝑛 - 𝑟

are Theorem 4.2.7 and rank–nullity. For

𝐴^{𝖳} \in 𝐹^{𝑛 \times 𝑚}

rank 𝐴^{𝖳} = 𝑟

and rank–nullity gives

dim ker 𝐴^{𝖳} = 𝑚 - 𝑟

. (b) The first two bases are Theorem 4.2.7 and Remark 3.4.11, and the third is the second proof of Theorem 4.3.8. The last

𝑚 - 𝑟

rows of

𝐺

, transposed, span

ker 𝐴^{𝖳}

by Exercise 3.3.57, and

𝑚 - 𝑟

vectors spanning a space of dimension

𝑚 - 𝑟

form a basis.

(a) By Theorem 4.2.7 and Theorem 4.2.11(a), $dim im 𝐴 = 𝑟$ and $dim ker 𝐴 = 𝑛 - 𝑟$ . The transpose $𝐴^{𝖳} \in 𝐹^{𝑛 \times 𝑚}$ has $𝑚$ columns and rank $𝑟$ (Theorem 4.3.8), so $dim im 𝐴^{𝖳} = 𝑟$ and $dim ker 𝐴^{𝖳} = 𝑚 - 𝑟$ , by the same two results applied to $𝐴^{𝖳}$ .

(b) The pivot columns of $𝐴$ form a basis of $im 𝐴$ by Theorem 4.2.7, and the basic solutions form a basis of $ker 𝐴$ by Remark 3.4.11. The nonzero rows of $𝐴_{𝑟}$ , transposed, form a basis of $im 𝐴^{𝖳}$ , as shown in the second proof of Theorem 4.3.8. Finally, $𝐲 \in ker 𝐴^{𝖳}$ if and only if $𝐲^{𝖳} 𝐴 = 𝟎^{𝖳}$ , that is, $𝐲^{𝖳}$ is a relation among the rows of $𝐴$ . By Exercise 3.3.57, these relations are exactly the linear combinations of the last $𝑚 - 𝑟$ rows of $𝐺$ . So the transposes of these $𝑚 - 𝑟$ rows span $ker 𝐴^{𝖳}$ , a space of dimension $𝑚 - 𝑟$ by (a), and they form a basis by Corollary 4.1.11(b). □

Subspace	Dimension	Basis, from $𝐺 𝐴 = 𝐴_{𝑟}$
$im 𝐴 \subseteq 𝐹^{𝑚}$	$𝑟$	the pivot columns of $𝐴$
$ker 𝐴 \subseteq 𝐹^{𝑛}$	$𝑛 - 𝑟$	the basic solutions
$im 𝐴^{𝖳} \subseteq 𝐹^{𝑛}$	$𝑟$	the nonzero rows of $𝐴_{𝑟}$
$ker 𝐴^{𝖳} \subseteq 𝐹^{𝑚}$	$𝑚 - 𝑟$	the last $𝑚 - 𝑟$ rows of $𝐺$

Table 4.3.1. The four fundamental subspaces of

𝐴 \in 𝐹^{𝑚 \times 𝑛}

of rank

𝑟

(Proposition 4.3.13). Rows are written as columns. The two subspaces of

𝐹^{𝑛}

have dimensions adding to

𝑛

, and the two subspaces of

𝐹^{𝑚}

have dimensions adding to

𝑚

Example 4.3.14 (The four subspaces of a $3 \times 4$ matrix). Take the matrix of Intuition (Why this is surprising),

𝐴 = (\begin{matrix} 1 & 2 & 1 & 4 \\ 2 & 4 & 0 & 6 \\ 1 & 2 & - 1 & 2 \end{matrix}), 𝐴_{𝑟} = (\begin{matrix} 1 & 2 & 0 & 3 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{matrix}) .

Here $𝑚 = 3$ , $𝑛 = 4$ , $𝑟 = 2$ , and the pivot columns are $1$ and $3$ .

Column space. Columns $1$ and $3$ of $𝐴$ : $im 𝐴 =$ $span ((1, 2, 1), (1, 0, - 1))$ , of dimension $2$ .
Null space. The free columns are $2$ and $4$ , with basic solutions $(- 2, 1, 0, 0)$ and $(- 3, 0, - 1, 1)$ , so $dim ker 𝐴 = 2$ .
Row space. The nonzero rows of $𝐴_{𝑟}$ : $im 𝐴^{𝖳} =$ $span ((1, 2, 0, 3), (0, 0, 1, 1))$ , of dimension $2$ .
Left null space. The relation ${row}_{1} - {row}_{2} + {row}_{3} = 𝟎$ gives $(1, - 1, 1) \in ker 𝐴^{𝖳}$ , and $dim ker 𝐴^{𝖳} = 3 - 2 = 1$ , so $ker 𝐴^{𝖳} =$ $span ((1, - 1, 1))$ .

The dimensions are $2 + 2 = 4 = 𝑛$ in $𝐹^{𝑛}$ and $2 + 1 = 3 = 𝑚$ in $𝐹^{𝑚}$ .

In this example something more is true. Every vector of the row space has dot product $0$ with every vector of the null space: for instance $(1, 2, 0, 3) \cdot$ $(- 3, 0, - 1, 1) =$ $- 3 +$ $3 =$ $0$ . Likewise $(1, 2, 1) \cdot$ $(1, - 1, 1) =$ $0 =$ $(1, 0, - 1) \cdot$ $(1, - 1, 1)$ . This always happens. Writing $𝐮 \cdot$ $𝐱 =$ $𝑢_{1} 𝑥_{1} +$ $\dots +$ $𝑢_{𝑛} 𝑥_{𝑛}$ , entry $𝑖$ of $𝐴 𝐱$ is (row $𝑖$ ) $\cdot 𝐱$ , so $𝐱 \in ker 𝐴$ exactly when every vector of the row space has dot product $0$ with $𝐱$ (Exercise 3.3.50(a)); applied to $𝐴^{𝖳}$ , the same holds for the column space and the left null space. Over $ℝ$ , the row space and the null space are then orthogonal complements in $ℝ^{𝑛}$ : they meet only in $𝟎$ , and together they span $ℝ^{𝑛}$ . So $ℝ^{𝑛}$ splits into two perpendicular pieces, of dimensions $𝑟$ and $𝑛 - 𝑟$ , and $ℝ^{𝑚}$ into two perpendicular pieces of dimensions $𝑟$ and $𝑚 - 𝑟$ . This picture is behind least squares (Section 6.5), and it is proved in Section 6.6 (Theorem 6.6.21). Over some other fields, such as $𝔽_{2}$ and $ℂ$ , the dimensions still add up, but the two pieces can overlap.

Non-example 4.3.15 (Row space and null space can overlap). Over $𝔽_{2}$ , let $𝐴 = (\begin{matrix} 1 & 1 \end{matrix})$ . Its row space is $span ((1, 1))$ , and $(1, 1)$ lies in $ker 𝐴$ , since $1 + 1 = 0$ . So $im 𝐴^{𝖳} = ker 𝐴$ : the two subspaces of $𝔽_{2}^{2}$ coincide, although their dimensions $1 + 1 = 2$ add up correctly.

Over $ℂ$ , let $𝐴 = (\begin{matrix} 1 & 𝑖 \end{matrix})$ . Then $(1, 𝑖) \in im 𝐴^{𝖳}$ , and $𝐴 (1, 𝑖) = 1 + 𝑖^{2} = 0$ , so $(1, 𝑖) \in ker 𝐴$ as well. Over $ℂ$ the cure is to replace $𝐴^{𝖳}$ by the conjugate transpose $𝐴^{*}$ of Definition 6.3.26: the column space of $𝐴^{*}$ meets $ker 𝐴$ only in $𝟎$ (Section 6.6). Over $𝔽_{2}$ no such repair exists: for every symmetric bilinear pairing on $𝔽_{2}^{𝑛}$ with $𝑛 \geq 2$ , some nonzero vector pairs to $0$ with itself (Section 12.4).

4.3.5Rank-one matrices and sums

The simplest nonzero matrices have rank one. In

(\begin{matrix} 2 & - 1 \\ 4 & - 2 \end{matrix}) = (\begin{matrix} 1 \\ 2 \end{matrix}) (\begin{matrix} 2 & - 1 \end{matrix}),

every column is a multiple of $(1, 2)$ and every row is a multiple of $(2, - 1)$ , and the matrix is the product of these two vectors.

Proposition 4.3.16 (Rank-one matrices). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. Then

rank 𝐴 = 1

if and only if

𝐴 = 𝐮 𝐯^{𝖳}

for some nonzero

𝐮 \in 𝐹^{𝑚}

and

𝐯 \in 𝐹^{𝑛}

. In that case

im 𝐴 = span (𝐮)

and

im 𝐴^{𝖳} = span (𝐯)

, and if also

𝐴 = 𝐮^{'} 𝐯^{' 𝖳}

, then

𝐮^{'} = 𝑐 𝐮

and

𝐯^{'} = 𝑐^{- 1} 𝐯

for some nonzero

𝑐 \in 𝐹

Proof.routine

Uses. Proposition 2.4.8 (Four views of the product), Proposition 2.6.18 (The column space is spanned by the columns), Proposition 1.2.35 (Zero products), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ), Proposition 2.4.23 (Transpose of a product)

Hint 1. Column

𝑗

𝐮 𝐯^{𝖳}

𝑣_{𝑗} 𝐮

. What does this say about

im (𝐮 𝐯^{𝖳})

Hint 2. Conversely, if

rank 𝐴 = 1

, then

im 𝐴 = span (𝐮)

for some

𝐮 \neq 𝟎

. Write each column of

𝐴

as a multiple of

𝐮

Hint 3. For uniqueness,

𝐮^{'}

lies in

im 𝐴 = span (𝐮)

. Then compare

𝐮 𝐯^{𝖳}

with

𝐮^{'} 𝐯^{' 𝖳}

in a row where

𝐮

is nonzero.

Sketch. Column

𝑗

𝐮 𝐯^{𝖳}

𝑣_{𝑗} 𝐮

, so

im (𝐮 𝐯^{𝖳}) =

span (𝐮)

when

𝐯 \neq 𝟎

, a line. If

rank 𝐴 = 1

, then

im 𝐴 = span (𝐮)

, so column

𝑗

𝑣_{𝑗} 𝐮

for some

𝑣_{𝑗}

, and

𝐴 = 𝐮 𝐯^{𝖳}

. Transposing gives the row space. If

𝐮 𝐯^{𝖳} = 𝐮^{'} 𝐯^{' 𝖳}

, then

span (𝐮^{'}) =

span (𝐮)

, so

𝐮^{'} = 𝑐 𝐮

, and row

𝑖

with

𝑢_{𝑖} \neq 0

gives

𝐯 = 𝑐 𝐯^{'}

If. Let $𝐮 \neq 𝟎$ and $𝐯 \neq 𝟎$ . By the column view (Proposition 2.4.8(b)), column $𝑗$ of $𝐮 𝐯^{𝖳}$ is $𝑣_{𝑗} 𝐮$ . So every column lies in $span (𝐮)$ , and $im (𝐮 𝐯^{𝖳}) \subseteq$ $span (𝐮)$ by Proposition 2.6.18. Some $𝑣_{𝑗}$ is nonzero, and then $𝑣_{𝑗} 𝐮 \neq 𝟎$ (Proposition 1.2.35), so $im (𝐮 𝐯^{𝖳})$ is a nonzero subspace of the line $span (𝐮)$ , hence equal to it. So $rank (𝐮 𝐯^{𝖳}) = 1$ (Theorem 4.2.7) and $im 𝐴 = span (𝐮)$ .

Only if. Let $rank 𝐴 = 1$ . Then $im 𝐴$ is one-dimensional, so $im 𝐴 = span (𝐮)$ for any nonzero $𝐮 \in im 𝐴$ . Each column $𝐚_{𝑗}$ lies in $im 𝐴$ , so $𝐚_{𝑗} = 𝑣_{𝑗} 𝐮$ for some $𝑣_{𝑗} \in 𝐹$ . With $𝐯 = (𝑣_{1}, \dots, 𝑣_{𝑛})$ , column $𝑗$ of $𝐮 𝐯^{𝖳}$ is $𝑣_{𝑗} 𝐮 = 𝐚_{𝑗}$ , so $𝐴 = 𝐮 𝐯^{𝖳}$ . And $𝐯 \neq 𝟎$ , since $𝐴 \neq 0$ .

The row space and uniqueness. By Proposition 2.4.23, $𝐴^{𝖳} = 𝐯 𝐮^{𝖳}$ , so $im 𝐴^{𝖳} = span (𝐯)$ by the first paragraph. If also $𝐴 = 𝐮^{'} 𝐯^{' 𝖳}$ with $𝐮^{'}, 𝐯^{'}$ nonzero, then $span (𝐮^{'}) =$ $im 𝐴 =$ $span (𝐮)$ , so $𝐮^{'} = 𝑐 𝐮$ with $𝑐 \neq 0$ . Then $𝐮 {(𝐯 - 𝑐 𝐯^{'})}^{𝖳} =$ $𝐮 𝐯^{𝖳} -$ $𝐮^{'} 𝐯^{' 𝖳} =$ $0$ . Choose $𝑖$ with $𝑢_{𝑖} \neq 0$ . By the row view (Proposition 2.4.8(c)), row $𝑖$ of the left side is $𝑢_{𝑖} {(𝐯 - 𝑐 𝐯^{'})}^{𝖳}$ , which is therefore zero, so $𝐯 = 𝑐 𝐯^{'}$ , that is, $𝐯^{'} = 𝑐^{- 1} 𝐯$ . □

The rank normal form gives the same factorization in one line: if $𝐺 𝐴 𝐻 =$ $𝑁_{1} =$ $𝐞_{1} 𝐞_{1}^{𝖳}$ , then $𝐴 =$ $(𝐺^{- 1} 𝐞_{1}) (𝐞_{1}^{𝖳} 𝐻^{- 1})$ , a column of $𝐺^{- 1}$ times a row of $𝐻^{- 1}$ . The form $𝐮 𝐯^{𝖳}$ is worth reaching for whenever rank one appears.

Technique 4.3.17 (Write a rank-one matrix as $𝐮 𝐯^{𝖳}$ ). A matrix of rank one is $𝐮 𝐯^{𝖳}$ with $𝐮, 𝐯 \neq 𝟎$ (Proposition 4.3.16). In this form products collapse to scalars, because $𝐯^{𝖳} 𝐰$ is a $1 \times 1$ matrix and can be moved out of the way:

\begin{aligned} (𝐮 𝐯^{𝖳}) 𝐱 & = (𝐯^{𝖳} 𝐱) 𝐮, \\ (𝐮 𝐯^{𝖳}) (𝐰 𝐳^{𝖳}) & = (𝐯^{𝖳} 𝐰) 𝐮 𝐳^{𝖳}, \\ {(𝐮 𝐯^{𝖳})}^{2} & = (𝐯^{𝖳} 𝐮) 𝐮 𝐯^{𝖳} . \end{aligned}

Reach for it when a hypothesis says that a matrix has rank one, when a matrix differs from a known one by a rank-one matrix (as $𝐼_{𝑛} + 𝐮 𝐯^{𝖳}$ or $𝐴 + 𝐮 𝐯^{𝖳}$ do), and when a matrix is to be split into simple pieces. The canonical example is Proposition 4.3.16, and Example 4.3.18 shows the collapse at work. Later instances are the matrix determinant lemma for $det (𝐴 + 𝐮 𝐯^{𝖳})$ (Theorem 5.5.27) and the singular value decomposition, which writes every matrix as a sum of rank-one pieces in the best possible way (Section 9.1).

Used in 12 places and 7 practice exercises

Exercise 4.3.19, Corollary 4.3.24, Exercise 4.3.37, Exercise 4.3.38, Exercise 4.3.39, Exercise 4.3.40, Exercise 4.3.41, Exercise 4.5.51, Exercise 7.4.40, Problem 7.7, Problem 7.13, Exercise 8.1.26; 7 practice exercises.

Example 4.3.18 (Powers of a rank-one matrix). Let $𝐴 = 𝐮 𝐯^{𝖳} \in 𝐹^{𝑛 \times 𝑛}$ have rank one. Its diagonal entries are $𝑢_{𝑖} 𝑣_{𝑖}$ , so $𝐯^{𝖳} 𝐮 =$ $𝑢_{1} 𝑣_{1} +$ $\dots +$ $𝑢_{𝑛} 𝑣_{𝑛} =$ $tr 𝐴$ . By Technique 4.3.17,

𝐴^{2} = 𝐮 (𝐯^{𝖳} 𝐮) 𝐯^{𝖳} = (tr 𝐴) 𝐴,

and by induction $𝐴^{𝑘} = {(tr 𝐴)}^{𝑘 - 1} 𝐴$ for $𝑘 \geq 1$ . So a rank-one matrix is nilpotent if and only if $tr 𝐴 = 0$ , in which case already $𝐴^{2} = 0$ ; and $𝐴^{2} = 𝐴$ if and only if $tr 𝐴 = 1$ , since $𝐴 \neq 0$ . For instance $(\begin{matrix} 2 & - 1 \\ 4 & - 2 \end{matrix}) =$ $(\begin{matrix} 1 \\ 2 \end{matrix}) (\begin{matrix} 2 & - 1 \end{matrix})$ has trace $0$ , and its square is $0$ ; while $(\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}) = 𝐞_{1} (\begin{matrix} 1 & 1 \end{matrix})$ has trace $1$ and equals its square.

Exercise 4.3.19.routine Let $𝐴 = (\begin{matrix} 3 & 1 & 1 \\ 6 & 2 & 2 \\ - 3 & - 1 & - 1 \end{matrix})$ .

(a)Over $ℚ$ , show that $rank 𝐴 = 1$ by writing $𝐴 = 𝐮 𝐯^{𝖳}$ , and compute $𝐴^{10}$ .
(b)Over $𝔽_{2}$ , compute $𝐴^{2}$ .

Solution.

Uses. Proposition 4.3.16 (Rank-one matrices), Example 4.3.18 (Powers of a rank-one matrix)

Techniques. Write a rank-one matrix as $𝐮 𝐯^{𝖳}$ (Technique 4.3.17)

Hint 1. Every row is a multiple of

(3, 1, 1)

Hint 2.

𝐴^{𝑘} = {(tr 𝐴)}^{𝑘 - 1} 𝐴

. Over

𝔽_{2}

, reduce the trace modulo

2

Sketch. (a)

𝐴 =

(1, 2, - 1) {(3, 1, 1)}^{𝖳}

, so

rank 𝐴 = 1

tr 𝐴 = 3 + 2 - 1 = 4

, and

𝐴^{10} =

4^{9} 𝐴 =

262144 𝐴

. (b) Over

𝔽_{2}

tr 𝐴 = 0

, so

𝐴^{2} = 0

(a) The rows are $1$ , $2$ , and $- 1$ times $(3, 1, 1)$ , so $𝐴 = 𝐮 𝐯^{𝖳}$ with $𝐮 = (1, 2, - 1)$ and $𝐯 = (3, 1, 1)$ , both nonzero, and $rank 𝐴 = 1$ by Proposition 4.3.16. Its trace is $3 + 2 - 1 = 4$ , so by Example 4.3.18, $𝐴^{10} =$ $4^{9} 𝐴 =$ $262144 𝐴$ .

(b) Over $𝔽_{2}$ , $𝐴 =$ $(\begin{matrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ 1 & 1 & 1 \end{matrix}) =$ $(1, 0, 1) {(1, 1, 1)}^{𝖳}$ , of rank one, with $tr 𝐴 = 1 + 0 + 1 = 0$ . So $𝐴^{2} = (tr 𝐴) 𝐴 = 0$ . Directly: $(1, 1, 1) \cdot$ $(1, 0, 1) =$ $2 =$ $0$ in $𝔽_{2}$ .

For sums, the image of $𝐴 + 𝐵$ lies inside $im 𝐴 + im 𝐵$ , which gives an upper bound but no exact formula.

Proposition 4.3.20 (Rank is subadditive). For $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ ,

rank (𝐴 + 𝐵) \leq rank 𝐴 + rank 𝐵 .

Proof (comparing images).routine

Uses. Proposition 1.4.24 (The sum of two subspaces), Proposition 4.1.21 (Dimensions of subspaces), Corollary 4.1.11 (Spanning lists are long)

Hint 1.

(𝐴 + 𝐵) 𝐱 =

𝐴 𝐱 +

𝐵 𝐱

. Which subspace contains

im (𝐴 + 𝐵)

Hint 2. Concatenate a basis of

im 𝐴

and a basis of

im 𝐵

Sketch. Every

(𝐴 + 𝐵) 𝐱 =

𝐴 𝐱 +

𝐵 𝐱

lies in

im 𝐴 + im 𝐵

, which is spanned by a basis of

im 𝐴

followed by a basis of

im 𝐵

, a list of length

rank 𝐴 + rank 𝐵

For every $𝐱 \in 𝐹^{𝑛}$ , $(𝐴 + 𝐵) 𝐱 =$ $𝐴 𝐱 +$ $𝐵 𝐱 \in$ $im 𝐴 +$ $im 𝐵$ , so $im (𝐴 + 𝐵) \subseteq$ $im 𝐴 +$ $im 𝐵$ , a subspace of $𝐹^{𝑚}$ (Proposition 1.4.24). Let $𝐚_{1}, \dots, 𝐚_{𝑘}$ and $𝐛_{1}, \dots, 𝐛_{𝑙}$ be bases of $im 𝐴$ and $im 𝐵$ . Every vector of $im 𝐴 + im 𝐵$ is a sum of a combination of the $𝐚_{𝑖}$ and a combination of the $𝐛_{𝑗}$ , so the list $𝐚_{1},$ $\dots,$ $𝐚_{𝑘},$ $𝐛_{1},$ $\dots,$ $𝐛_{𝑙}$ spans $im 𝐴 + im 𝐵$ , and $dim (im 𝐴 + im 𝐵) \leq$ $𝑘 +$ $𝑙$ (Corollary 4.1.11(a)). Hence

\begin{aligned} rank (𝐴 + 𝐵) & \leq dim (im 𝐴 + im 𝐵) \\ \leq 𝑘 + 𝑙 = rank 𝐴 + rank 𝐵 \end{aligned}

by Proposition 4.1.21(a). □

Proof (comparing kernels).routine

Uses. Proposition 4.2.26 (Subspaces that must meet), Theorem 4.2.11 (Rank–nullity), Proposition 4.1.21 (Dimensions of subspaces)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1.

ker 𝐴 \cap

ker 𝐵 \subseteq

ker (𝐴 + 𝐵)

Hint 2. How large must

ker 𝐴 \cap ker 𝐵

be? Use Proposition 4.2.26 in

𝐹^{𝑛}

Sketch.

ker 𝐴 \cap

ker 𝐵 \subseteq

ker (𝐴 + 𝐵)

, and by Proposition 4.2.26,

dim (ker 𝐴 \cap ker 𝐵) \geq

(𝑛 - rank 𝐴) +

(𝑛 - rank 𝐵) -

𝑛

. So

dim ker (𝐴 + 𝐵) \geq

𝑛 -

rank 𝐴 -

rank 𝐵

, and rank–nullity gives the claim.

If $𝐴 𝐱 = 𝐵 𝐱 = 𝟎$ , then $(𝐴 + 𝐵) 𝐱 = 𝟎$ , so $ker 𝐴 \cap$ $ker 𝐵 \subseteq$ $ker (𝐴 + 𝐵)$ . By Proposition 4.1.21(a), Proposition 4.2.26 in $𝐹^{𝑛}$ , and Theorem 4.2.11(a),

\begin{aligned} dim ker (𝐴 + 𝐵) & \geq dim (ker 𝐴 \cap ker 𝐵) \\ \geq (𝑛 - rank 𝐴) + (𝑛 - rank 𝐵) - 𝑛 \\ = 𝑛 - rank 𝐴 - rank 𝐵 . \end{aligned}

By Theorem 4.2.11(a) again, $rank (𝐴 + 𝐵) =$ $𝑛 -$ $dim ker (𝐴 + 𝐵) \leq$ $rank 𝐴 +$ $rank 𝐵$ . □

As for products, the image proof works in the target and the kernel proof in the domain. On the kernel side, the inequality is the statement that two large subspaces of $𝐹^{𝑛}$ must overlap (Proposition 4.2.26).

By induction on $𝑘$ , a sum of $𝑘$ matrices of rank one has rank at most $𝑘$ . The next subsection shows that this bound is attained: every matrix of rank $𝑟$ is a sum of $𝑟$ matrices of rank one.

4.3.6The column–row factorization

The pivot columns of $𝐴$ form a basis of $im 𝐴$ (Theorem 4.2.7), so every column of $𝐴$ is a combination of them, and the coefficients can be read off $rref (𝐴)$ (Lemma 3.3.16(d), Corollary 3.2.17). Recording all these combinations at once is a matrix product.

Theorem 4.3.21 (Column–row factorization). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have rank $𝑟 \geq 1$ and pivot columns $𝑝_{1} < \dots < 𝑝_{𝑟}$ . Let $𝐶 \in 𝐹^{𝑚 \times 𝑟}$ be the matrix whose columns are the pivot columns $𝐚_{𝑝_{1}}, \dots, 𝐚_{𝑝_{𝑟}}$ of $𝐴$ , and let $𝑅 \in 𝐹^{𝑟 \times 𝑛}$ consist of the first $𝑟$ rows of $rref (𝐴)$ , which are its nonzero rows. Then

𝐴 = 𝐶 𝑅 .

Moreover, the columns of $𝐶$ form a basis of $im 𝐴$ , and the rows of $𝑅$ , written as columns, form a basis of $im 𝐴^{𝖳}$ . In particular $rank 𝐶 = rank 𝑅 = 𝑟$ .

Proof.routine

Uses. Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Proposition 3.3.8 (Properties of the output), Theorem 2.4.34 (Block multiplication), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Definition 2.4.1 (Matrix product), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ), Theorem 4.3.8 (Row rank equals column rank), Theorem 3.3.12 (Matrices in RREF)

Hint 1. Write

𝐴 = 𝐺^{- 1} 𝐴_{𝑟}

, where

𝐴_{𝑟} = (\begin{matrix} 𝑅 \\ 0 \end{matrix})

in block form.

Hint 2. Split

𝐺^{- 1}

into its first

𝑟

columns and the rest, and multiply in blocks. Then identify column

𝑠

𝐺^{- 1}

by looking at column

𝑝_{𝑠}

𝐴 = 𝐺^{- 1} 𝐴_{𝑟}

Sketch.

𝐺 𝐴 = 𝐴_{𝑟} = (\begin{matrix} 𝑅 \\ 0 \end{matrix})

. With

𝐺^{- 1} = (\begin{matrix} 𝐶^{'} & 𝐶^{″} \end{matrix})

split after

𝑟

columns, block multiplication gives

𝐴 = 𝐶^{'} 𝑅

. Column

𝑠

𝐶^{'}

𝐺^{- 1} 𝐞_{𝑠}

, and since column

𝑝_{𝑠}

𝐴_{𝑟}

𝐞_{𝑠}

, column

𝑝_{𝑠}

𝐴

is also

𝐺^{- 1} 𝐞_{𝑠}

; so

𝐶^{'} = 𝐶

. The basis statements are Theorem 4.2.7 and the second proof of Theorem 4.3.8.

Let $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ (Theorem 3.3.10). By Proposition 3.3.8(a), rows $𝑟 + 1, \dots, 𝑚$ of $𝐴_{𝑟}$ are zero, so in block form $𝐴_{𝑟} = (\begin{matrix} 𝑅 \\ 0 \end{matrix})$ , with a zero block of $𝑚 - 𝑟$ rows. Split $𝐺^{- 1} = (\begin{matrix} 𝐶^{'} & 𝐶^{″} \end{matrix})$ , where $𝐶^{'} \in 𝐹^{𝑚 \times 𝑟}$ consists of the first $𝑟$ columns of $𝐺^{- 1}$ . By Theorem 2.4.34,

𝐴 = 𝐺^{- 1} 𝐴_{𝑟} = (\begin{matrix} 𝐶^{'} & 𝐶^{″} \end{matrix}) (\begin{matrix} 𝑅 \\ 0 \end{matrix}) = 𝐶^{'} 𝑅 + 𝐶^{″} 0 = 𝐶^{'} 𝑅 .

Column $𝑠$ of $𝐶^{'}$ is $𝐺^{- 1} 𝐞_{𝑠}$ . Column $𝑝_{𝑠}$ of $𝐴_{𝑟}$ is $𝐞_{𝑠}$ (Lemma 3.3.16(b)), so column $𝑝_{𝑠}$ of $𝐴 = 𝐺^{- 1} 𝐴_{𝑟}$ is $𝐺^{- 1} 𝐞_{𝑠}$ (Definition 2.4.1). Hence column $𝑠$ of $𝐶^{'}$ is $𝐚_{𝑝_{𝑠}}$ , that is, $𝐶^{'} = 𝐶$ , and $𝐴 = 𝐶 𝑅$ .

The columns of $𝐶$ form a basis of $im 𝐴$ by Theorem 4.2.7, so $rank 𝐶 = 𝑟$ . The rows of $𝑅$ are the nonzero rows of $𝐴_{𝑟}$ , and the second proof of Theorem 4.3.8 showed that, written as columns, they form a basis of $im 𝐴^{𝖳}$ . Finally, $𝑅$ satisfies (R1)–(R4) with $𝑟$ pivots, so it is in RREF and $rank 𝑅 = 𝑟$ (Theorem 3.3.12). □

Read column by column (Proposition 2.4.8(b)), $𝐴 = 𝐶 𝑅$ says that column $𝑗$ of $𝐴$ is the combination of the pivot columns of $𝐴$ whose coefficients are column $𝑗$ of $rref (𝐴)$ :

𝐚_{𝑗} = 𝑅_{1 𝑗} 𝐚_{𝑝_{1}} + \dots + 𝑅_{𝑟 𝑗} 𝐚_{𝑝_{𝑟}} .

This is Corollary 3.2.17 once more: the free columns of $rref (𝐴)$ record how the free columns of $𝐴$ are built from its pivot columns.

Example 4.3.22 (A column–row factorization). For the matrix $𝐴$ of Example 4.3.14, the pivot columns are $1$ and $3$ , so $𝐴 = 𝐶 𝑅$ with

𝐶 = (\begin{matrix} 1 & 1 \\ 2 & 0 \\ 1 & - 1 \end{matrix}), 𝑅 = (\begin{matrix} 1 & 2 & 0 & 3 \\ 0 & 0 & 1 & 1 \end{matrix}) .

Column $4$ of $𝑅$ is $(3, 1)$ , and indeed $𝐚_{4} = 3 𝐚_{1} + 𝐚_{3}$ ; column $2$ of $𝑅$ is $(2, 0)$ , and $𝐚_{2} = 2 𝐚_{1}$ . By the column–row view of the product (Proposition 2.4.8(d)), $𝐴$ is a sum of two matrices of rank one:

\begin{aligned} 𝐴 & = (\begin{matrix} 1 \\ 2 \\ 1 \end{matrix}) (\begin{matrix} 1 & 2 & 0 & 3 \end{matrix}) + (\begin{matrix} 1 \\ 0 \\ - 1 \end{matrix}) (\begin{matrix} 0 & 0 & 1 & 1 \end{matrix}) \\ = (\begin{matrix} 1 & 2 & 0 & 3 \\ 2 & 4 & 0 & 6 \\ 1 & 2 & 0 & 3 \end{matrix}) + (\begin{matrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & - 1 & - 1 \end{matrix}) . \end{aligned}

(\begin{matrix} 1 & 2 & 1 & 4 \\ 2 & 4 & 0 & 6 \\ 1 & 2 & - 1 & 2 \end{matrix}) ⇝ (\begin{matrix} 1 & 2 & 0 & 3 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{matrix})

The reduction of Example 4.3.22. At the end, the pivot columns listed in the summary pick out the columns of

𝐴

that form

𝐶

, and the nonzero rows of the final matrix form

𝑅

. Use “Edit” to try your own matrix: the number of pivots is both the number of columns of

𝐶

and the number of rows of

𝑅

The column–row factorization is one of many factorizations of $𝐴$ through $𝐹^{𝑟}$ , and the next proposition says that all of them carry the same information.

Proposition 4.3.23 (Factorizations through

𝐹^{𝑘}

). Let

𝐴 = 𝑋 𝑌

with

𝑋 \in 𝐹^{𝑚 \times 𝑘}

and

𝑌 \in 𝐹^{𝑘 \times 𝑛}

(a) $rank 𝐴 \leq 𝑘$ .
(b)If $𝑘 = rank 𝐴$ , then the columns of $𝑋$ form a basis of $im 𝐴$ , and the rows of $𝑌$ , written as columns, form a basis of $im 𝐴^{𝖳}$ .

Proof.routine

Uses. Theorem 4.3.3 (Rank of a product), Proposition 3.5.2 (First properties of rank), Proposition 2.6.18 (The column space is spanned by the columns), Proposition 4.1.21 (Dimensions of subspaces), Corollary 4.1.11 (Spanning lists are long), Proposition 2.4.23 (Transpose of a product), Theorem 4.3.8 (Row rank equals column rank)

Techniques. Dimension counting (Technique 4.2.24), Transpose to trade rows for columns (Technique 3.2.27)

Hint 1.

𝑋

has only

𝑘

columns.

Hint 2. For (b),

im 𝐴 \subseteq im 𝑋

, and

im 𝑋

is spanned by

𝑘

vectors. Compare dimensions. For

𝑌

, transpose.

Sketch. (a)

rank 𝐴 \leq rank 𝑋 \leq 𝑘

. (b)

im 𝐴 \subseteq im 𝑋

, and

im 𝑋

is spanned by the

𝑘

columns of

𝑋

, so

dim im 𝑋 \leq

𝑘 =

dim im 𝐴

. Hence

im 𝐴 = im 𝑋

, and

𝑘

vectors spanning a

𝑘

-dimensional space form a basis. Apply the same argument to

𝐴^{𝖳} = 𝑌^{𝖳} 𝑋^{𝖳}

, of rank

𝑘

by Theorem 4.3.8.

(a) By Theorem 4.3.3 and Proposition 3.5.2(a), $rank 𝐴 =$ $rank (𝑋 𝑌) \leq$ $rank 𝑋 \leq$ $𝑘$ .

(b) Let $𝑘 = rank 𝐴$ . By Theorem 4.3.3, $im 𝐴 \subseteq im 𝑋$ , and $im 𝑋$ is spanned by the $𝑘$ columns of $𝑋$ (Proposition 2.6.18), so $dim im 𝑋 \leq$ $𝑘 =$ $dim im 𝐴$ (Corollary 4.1.11(a)). Also $dim im 𝐴 \leq dim im 𝑋$ (Proposition 4.1.21(a)), so the dimensions agree and $im 𝐴 = im 𝑋$ by Proposition 4.1.21(b). This is a space of dimension $𝑘$ spanned by the $𝑘$ columns of $𝑋$ ; so these columns form a basis of $im 𝐴$ (Corollary 4.1.11(b)). Next, $𝐴^{𝖳} = 𝑌^{𝖳} 𝑋^{𝖳}$ (Proposition 2.4.23), with $𝑌^{𝖳} \in 𝐹^{𝑛 \times 𝑘}$ , and $rank 𝐴^{𝖳} = 𝑘$ (Theorem 4.3.8). The argument just given, applied to $𝐴^{𝖳}$ , shows that the columns of $𝑌^{𝖳}$ , which are the rows of $𝑌$ written as columns, form a basis of $im 𝐴^{𝖳}$ . □

So in any factorization $𝐴 = 𝑋 𝑌$ with inner size $rank 𝐴$ , the left factor is a basis of the column space and the right factor a basis of the row space. Two such factorizations differ by an invertible $𝑟 \times 𝑟$ matrix (Exercise 4.3.44), and the column–row factorization is the one in which the right factor is in RREF. Every matrix of rank $𝑟$ is therefore a sum of $𝑟$ rank-one matrices, and Proposition 4.3.20 says that fewer will not do.

Corollary 4.3.24 (Rank as a number of rank-one pieces). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. Then

rank 𝐴

is the smallest

𝑘 \geq 0

such that

𝐴

is a sum of

𝑘

matrices of rank one (the empty sum being

0

Proof.routine

Uses. Theorem 4.3.21 (Column–row factorization), Proposition 2.4.8 (Four views of the product), Proposition 4.3.16 (Rank-one matrices), Proposition 4.3.20 (Rank is subadditive)

Techniques. Write a rank-one matrix as $𝐮 𝐯^{𝖳}$ (Technique 4.3.17)

Hint 1. For a decomposition with

rank 𝐴

terms, write

𝐴 = 𝐶 𝑅

and use the column–row view of the product.

Hint 2. For the lower bound, use Proposition 4.3.20 and induction on the number of terms.

Sketch. If

𝑟 = rank 𝐴 \geq 1

, then

𝐴 =

𝐶 𝑅 =

\sum_{𝑠 = 1}^{𝑟} 𝐜_{𝑠} 𝑅_{𝑠, \cdot}

, where

𝐜_{𝑠}

is column

𝑠

𝐶

and

𝑅_{𝑠, \cdot}

is row

𝑠

𝑅

; both are nonzero, so each term has rank one. Conversely, a sum of

𝑘

rank-one matrices has rank at most

𝑘

by subadditivity.

Let $𝑟 = rank 𝐴$ . If $𝑟 = 0$ , then $𝐴 = 0$ is the empty sum. If $𝑟 \geq 1$ , write $𝐴 = 𝐶 𝑅$ as in Theorem 4.3.21. By the column–row view (Proposition 2.4.8(d)),

𝐴 = 𝐜_{1} 𝑅_{1, \cdot} + \dots + 𝐜_{𝑟} 𝑅_{𝑟, \cdot},

where $𝐜_{𝑠}$ is column $𝑠$ of $𝐶$ and $𝑅_{𝑠, \cdot}$ is row $𝑠$ of $𝑅$ . Each $𝐜_{𝑠}$ is nonzero, as a vector of a basis, and each row of $𝑅$ is nonzero, as it contains a pivot. So each term has rank one by Proposition 4.3.16, and $𝐴$ is a sum of $𝑟$ matrices of rank one.

Conversely, if $𝐴 = 𝐴_{1} + \dots + 𝐴_{𝑘}$ with $rank 𝐴_{𝑖} = 1$ for each $𝑖$ , then by Proposition 4.3.20 and induction on $𝑘$ , $rank 𝐴 \leq$ $rank 𝐴_{1} +$ $\dots +$ $rank 𝐴_{𝑘} =$ $𝑘$ . So no sum of fewer than $𝑟$ rank-one matrices equals $𝐴$ . □

The lower bound can also be seen from Proposition 4.3.23(a): a sum $\sum_{𝑖 = 1}^{𝑘} 𝐮_{𝑖} 𝐯_{𝑖}^{𝖳}$ is the product of the $𝑚 \times 𝑘$ matrix with columns $𝐮_{𝑖}$ and the $𝑘 \times 𝑛$ matrix with rows $𝐯_{𝑖}^{𝖳}$ , so its rank is at most $𝑘$ . Storing $𝐶$ and $𝑅$ takes $𝑟 (𝑚 + 𝑛)$ numbers instead of the $𝑚 𝑛$ entries of $𝐴$ , which is far fewer when $𝑟$ is small. Low-rank approximation (Section 16.3) exploits this to compress data.

The factorization also gives a third proof of Theorem 4.3.8, the one in LADR. It never row reduces, and its idea is to prove an inequality for every matrix and then apply it to the transpose.

Proof of Theorem 4.3.8 (via a column–row factorization).routine

Uses. Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ), Proposition 2.4.8 (Four views of the product), Proposition 2.4.23 (Transpose of a product), Theorem 4.3.3 (Rank of a product), Proposition 3.5.2 (First properties of rank), Proposition 2.4.22 (Transpose is a linear involution)

Techniques. Transpose to trade rows for columns (Technique 3.2.27)

Hint 1. It suffices to prove

rank 𝐴^{𝖳} \leq rank 𝐴

for every matrix

𝐴

. Why?

Hint 2. Write

𝐴 = 𝐶 𝑅

with

𝐶

consisting of a basis of

im 𝐴

, so that

𝑅

has only

𝑟 = rank 𝐴

rows. What does

𝐴^{𝖳} = 𝑅^{𝖳} 𝐶^{𝖳}

say about

rank 𝐴^{𝖳}

Sketch. Let

𝑟 = rank 𝐴

and let

𝐶

have as columns a basis of

im 𝐴

. Every column of

𝐴

is a combination of these, so

𝐴 = 𝐶 𝑅

with

𝑅 \in 𝐹^{𝑟 \times 𝑛}

. Then

𝐴^{𝖳} = 𝑅^{𝖳} 𝐶^{𝖳}

, and

rank 𝐴^{𝖳} \leq

rank 𝑅^{𝖳} \leq

𝑟

, since

𝑅^{𝖳}

has

𝑟

columns. So

rank 𝐴^{𝖳} \leq rank 𝐴

for every

𝐴

; applied to

𝐴^{𝖳}

, it gives the reverse inequality.

We first show that $rank 𝐴^{𝖳} \leq rank 𝐴$ for every $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ . Let $𝑟 = rank 𝐴$ . If $𝑟 = 0$ , then $𝐴 = 0$ , so $𝐴^{𝖳} = 0$ and both ranks are $0$ . Otherwise let $𝐜_{1}, \dots, 𝐜_{𝑟}$ be a basis of $im 𝐴$ (for instance the pivot columns, Theorem 4.2.7), and let $𝐶 \in 𝐹^{𝑚 \times 𝑟}$ have these columns. Each column $𝐚_{𝑗}$ of $𝐴$ lies in $im 𝐴$ , so $𝐚_{𝑗} =$ $𝑥_{1 𝑗} 𝐜_{1} +$ $\dots +$ $𝑥_{𝑟 𝑗} 𝐜_{𝑟}$ for some scalars $𝑥_{𝑠 𝑗}$ . Let $𝑅 =$ $(𝑥_{𝑠 𝑗}) \in$ $𝐹^{𝑟 \times 𝑛}$ . By the column view (Proposition 2.4.8(b)), column $𝑗$ of $𝐶 𝑅$ is $\sum_{𝑠} 𝑥_{𝑠 𝑗} 𝐜_{𝑠} =$ $𝐚_{𝑗}$ , so $𝐴 = 𝐶 𝑅$ . Transposing, $𝐴^{𝖳} = 𝑅^{𝖳} 𝐶^{𝖳}$ (Proposition 2.4.23), and by Theorem 4.3.3 and Proposition 3.5.2(a),

rank 𝐴^{𝖳} \leq rank 𝑅^{𝖳} \leq 𝑟 = rank 𝐴,

since $𝑅^{𝖳} \in 𝐹^{𝑛 \times 𝑟}$ has only $𝑟$ columns.

Applying this to $𝐴^{𝖳}$ , whose transpose is $𝐴$ (Proposition 2.4.22), gives $rank 𝐴 \leq rank 𝐴^{𝖳}$ . Hence $rank 𝐴^{𝖳} = rank 𝐴$ . □

Intuition (Comparing the proofs that row rank equals column rank). The normal-form proof reduces

𝐴

to the simplest matrix of its rank and observes that transposing does not disturb it; the work was done in proving Theorem 3.5.27 and Proposition 4.3.1. The row-operation proof is the computational one: it finds a basis of the row space, and it explains the theorem through what row operations preserve. The factorization proof is the shortest, given Theorem 4.3.3, and it shows the mechanism most directly: every row of

𝐴 = 𝐶 𝑅

is a combination of the

𝑟

rows of

𝑅

, so the rows cannot span more than

𝑟

dimensions. Its last step, proving an inequality for all matrices and then applying it to the transpose to get the reverse inequality, is a pattern worth remembering.

Exercise 4.3.25.routine Find the column–row factorization of

𝐴 = (\begin{matrix} 1 & 𝑖 & 0 & 2 \\ 𝑖 & - 1 & 1 & 2 𝑖 \\ 1 + 𝑖 & - 1 + 𝑖 & 1 & 2 + 2 𝑖 \end{matrix}) \in ℂ^{3 \times 4},

and write $𝐴$ as a sum of $rank 𝐴$ matrices of rank one.

Solution.

Uses. Theorem 4.3.21 (Column–row factorization), Corollary 4.3.24 (Rank as a number of rank-one pieces)

Hint 1. Clear the first column with row

1

. Row

3

is the sum of rows

1

and

2

Hint 2. The pivot columns are

1

and

3

Sketch.

rref (𝐴) =

(\begin{matrix} 1 & 𝑖 & 0 & 2 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{matrix})

, with pivot columns

1, 3

. So

𝐶 = (\begin{matrix} 1 & 0 \\ 𝑖 & 1 \\ 1 + 𝑖 & 1 \end{matrix})

𝑅 = (\begin{matrix} 1 & 𝑖 & 0 & 2 \\ 0 & 0 & 1 & 0 \end{matrix})

, and

𝐴 =

(1, 𝑖, 1 + 𝑖) (\begin{matrix} 1 & 𝑖 & 0 & 2 \end{matrix}) +

(0, 1, 1) (\begin{matrix} 0 & 0 & 1 & 0 \end{matrix})

Adding $- 𝑖$ times row $1$ to row $2$ gives $(𝑖 - 𝑖, - 1 - 𝑖^{2}, 1, 2 𝑖 - 2 𝑖) =$ $(0, 0, 1, 0)$ . Row $3$ is the sum of rows $1$ and $2$ of $𝐴$ , so adding $- 1$ times each of them to it gives $𝟎$ . Hence

rref (𝐴) = (\begin{matrix} 1 & 𝑖 & 0 & 2 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}),

with pivot columns $1$ and $3$ , and $rank 𝐴 = 2$ . By Theorem 4.3.21,

𝐴 = 𝐶 𝑅, 𝐶 = (\begin{matrix} 1 & 0 \\ 𝑖 & 1 \\ 1 + 𝑖 & 1 \end{matrix}), 𝑅 = (\begin{matrix} 1 & 𝑖 & 0 & 2 \\ 0 & 0 & 1 & 0 \end{matrix}) .

Check: column $2$ of $𝐶 𝑅$ is $𝑖 (1, 𝑖, 1 + 𝑖) =$ $(𝑖, - 1, - 1 + 𝑖)$ and column $4$ is $2 (1, 𝑖, 1 + 𝑖) =$ $(2, 2 𝑖, 2 + 2 𝑖)$ , the columns of $𝐴$ . By Corollary 4.3.24 and its proof,

𝐴 = (\begin{matrix} 1 \\ 𝑖 \\ 1 + 𝑖 \end{matrix}) (\begin{matrix} 1 & 𝑖 & 0 & 2 \end{matrix}) + (\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}) (\begin{matrix} 0 & 0 & 1 & 0 \end{matrix}) .

Exercises

Exercise 4.3.26.routine Over $ℚ$ , let

\begin{matrix} 𝐴 = (\begin{matrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 2 \end{matrix}), \\ 𝐵_{1} = (\begin{matrix} 1 & 0 \\ 1 & 1 \\ - 1 & 0 \end{matrix}), 𝐵_{2} = (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix}) . \end{matrix}

(a)Find $ker 𝐴$ , and for $𝑖 = 1, 2$ find $im 𝐵_{𝑖} \cap ker 𝐴$ . Use (4.3.1) to find $rank (𝐴 𝐵_{𝑖})$ , and check by computing $𝐴 𝐵_{𝑖}$ .
(b)Is there a matrix $𝐵 \in ℚ^{3 \times 2}$ of rank $2$ with $𝐴 𝐵 = 0$ ?

Solution.

Uses. Proposition 4.3.5 (Rank of a product, exactly), Theorem 4.2.11 (Rank–nullity)

Hint 1. Row

3

𝐴

is the sum of rows

1

and

2

, so

rank 𝐴 = 2

and

ker 𝐴

is a line.

Hint 2. For (b), how small can

rank (𝐴 𝐵)

be when

rank 𝐵 = 2

and

dim ker 𝐴 = 1

Sketch.

ker 𝐴 =

span ((1, 1, - 1))

im 𝐵_{1}

contains

(1, 1, - 1)

, so

im 𝐵_{1} \cap ker 𝐴 = ker 𝐴

and

rank (𝐴 𝐵_{1}) = 2 - 1 = 1

;

im 𝐵_{2} =

span (𝐞_{1}, 𝐞_{2})

misses it, so

rank (𝐴 𝐵_{2}) = 2

. (b) No:

rank (𝐴 𝐵) =

2 -

dim (im 𝐵 \cap ker 𝐴) \geq

2 -

1 =

1

(a) $𝐴 𝐱 = 𝟎$ means $𝑥_{1} + 𝑥_{3} = 0$ , $𝑥_{2} + 𝑥_{3} = 0$ , and $𝑥_{1} + 𝑥_{2} + 2 𝑥_{3} = 0$ , the third being the sum of the first two. So $ker 𝐴 =$ $span ((1, 1, - 1))$ and $rank 𝐴 = 2$ .

The first column of $𝐵_{1}$ is $(1, 1, - 1)$ , so $ker 𝐴 \subseteq im 𝐵_{1}$ and $im 𝐵_{1} \cap ker 𝐴 = ker 𝐴$ , of dimension $1$ . The columns of $𝐵_{1}$ are independent, so $rank 𝐵_{1} = 2$ , and (4.3.1) gives $rank (𝐴 𝐵_{1}) = 2 - 1 = 1$ . Indeed

𝐴 𝐵_{1} = (\begin{matrix} 1 - 1 & 0 \\ 1 - 1 & 1 \\ 1 + 1 - 2 & 1 \end{matrix}) = (\begin{matrix} 0 & 0 \\ 0 & 1 \\ 0 & 1 \end{matrix}),

which has rank $1$ .

$im 𝐵_{2} =$ $span (𝐞_{1}, 𝐞_{2})$ consists of the vectors with third entry $0$ , and the only such multiple of $(1, 1, - 1)$ is $𝟎$ . So $im 𝐵_{2} \cap ker 𝐴 = {𝟎}$ and $rank (𝐴 𝐵_{2}) = 2$ . Indeed $𝐴 𝐵_{2} = (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{matrix})$ , the first two columns of $𝐴$ , which are independent.

(b) No. If $rank 𝐵 = 2$ , then by (4.3.1), $rank (𝐴 𝐵) =$ $2 -$ $dim (im 𝐵 \cap ker 𝐴) \geq$ $2 -$ $dim ker 𝐴 =$ $1$ , so $𝐴 𝐵 \neq 0$ .

Exercise 4.3.27.routine Let $𝐴 = (\begin{matrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix})$ .

(a)Over $𝔽_{2}$ , find bases of the four fundamental subspaces of $𝐴$ , and check the dimensions against Proposition 4.3.13. Show that $im 𝐴^{𝖳} = ker 𝐴$ .
(b)Over $ℚ$ , do the same, and show that $im 𝐴^{𝖳} \cap ker 𝐴 = {𝟎}$ .

Solution.

Uses. Proposition 4.3.13 (Dimensions of the four subspaces), Definition 4.3.12 (The four fundamental subspaces)

Hint 1. Over either field, row

3

is the sum of rows

1

and

2

, and the first two rows are already in RREF.

Hint 2. Over

𝔽_{2}

, compare the basic solutions with the rows. Over

ℚ

, apply

𝐴

to a general vector

𝑎 (1, 1, 0, 0) +

𝑏 (0, 0, 1, 1)

of the row space.

Sketch. Over both fields

rref (𝐴) =

(\begin{matrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{matrix})

𝑟 = 2

, pivot columns

1, 3

. Over

𝔽_{2}

im 𝐴 =

span ((1, 0, 1), (0, 1, 1))

ker 𝐴 =

span ((1, 1, 0, 0), (0, 0, 1, 1)) =

im 𝐴^{𝖳}

ker 𝐴^{𝖳} =

span ((1, 1, 1))

. Over

ℚ

ker 𝐴 =

span ((- 1, 1, 0, 0), (0, 0, - 1, 1))

ker 𝐴^{𝖳} =

span ((1, 1, - 1))

, and

𝐴 (𝑎, 𝑎, 𝑏, 𝑏) =

(2 𝑎, 2 𝑏, 2 𝑎 + 2 𝑏)

vanishes only for

𝑎 = 𝑏 = 0

Over any field, row $3$ of $𝐴$ is the sum of rows $1$ and $2$ , so subtracting rows $1$ and $2$ from row $3$ gives

rref (𝐴) = (\begin{matrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{matrix}),

with $𝑟 = 2$ , pivot columns $1, 3$ , and free columns $2, 4$ . Here $𝑚 = 3$ and $𝑛 = 4$ , so Proposition 4.3.13 predicts dimensions $2$ , $2$ , $2$ , $1$ .

(a) Over $𝔽_{2}$ :

$im 𝐴$ has the basis $(1, 0, 1), (0, 1, 1)$ , columns $1$ and $3$ of $𝐴$ .
The basic solutions are $(- 1, 1, 0, 0) =$ $(1, 1, 0, 0)$ and $(0, 0, - 1, 1) =$ $(0, 0, 1, 1)$ , a basis of $ker 𝐴$ .
$im 𝐴^{𝖳}$ has the basis $(1, 1, 0, 0),$ $(0, 0, 1, 1)$ , the nonzero rows of $rref (𝐴)$ .
Row $1$ plus row $2$ plus row $3$ is $(2, 2, 2, 2) = 𝟎$ , so $(1, 1, 1) \in ker 𝐴^{𝖳}$ , which has dimension $3 - 2 = 1$ ; so $ker 𝐴^{𝖳} =$ $span ((1, 1, 1))$ .

The bases of $ker 𝐴$ and $im 𝐴^{𝖳}$ are the same list, so $im 𝐴^{𝖳} = ker 𝐴$ . Each row is “orthogonal” to itself: $(1, 1, 0, 0) \cdot$ $(1, 1, 0, 0) =$ $2 =$ $0$ in $𝔽_{2}$ .

(b) Over $ℚ$ , $im 𝐴 =$ $span ((1, 0, 1), (0, 1, 1))$ and $im 𝐴^{𝖳} =$ $span ((1, 1, 0, 0), (0, 0, 1, 1))$ as before. The basic solutions are now $(- 1, 1, 0, 0)$ and $(0, 0, - 1, 1)$ , and row $1$ plus row $2$ minus row $3$ is $𝟎$ , so $ker 𝐴^{𝖳} =$ $span ((1, 1, - 1))$ . A vector of the row space is $𝐰 = (𝑎, 𝑎, 𝑏, 𝑏)$ , and $𝐴 𝐰 =$ $(2 𝑎, 2 𝑏, 2 𝑎 + 2 𝑏)$ . This is $𝟎$ only if $𝑎 = 𝑏 = 0$ , since $2 \neq 0$ in $ℚ$ . So $im 𝐴^{𝖳} \cap ker 𝐴 = {𝟎}$ . The two computations differ only in whether $1 + 1 = 0$ .

Exercise 4.3.28.routine For each item, find a matrix with the given properties, or show that none exists.

(a) $𝐴 \in ℝ^{3 \times 3}$ with $im 𝐴 =$ $span ((1, 0, 1))$ and $ker 𝐴 =$ $span ((1, 1, 0), (0, 1, 1))$ .
(b) $𝐴 \in 𝐹^{2 \times 4}$ with $ker 𝐴 = span (𝐞_{1})$ .
(c) $𝐴 \in 𝐹^{3 \times 3}$ whose row space contains $(1, 1, 0)$ and whose null space contains $(1, 0, 0)$ .
(d) $𝐴 \in 𝐹^{2 \times 2}$ with $im 𝐴 = ker 𝐴$ .
(e) $𝐴 \in 𝐹^{3 \times 3}$ with $im 𝐴 = ker 𝐴$ .

Solution.

Uses. Proposition 4.3.16 (Rank-one matrices), Proposition 4.3.13 (Dimensions of the four subspaces), Theorem 4.2.11 (Rank–nullity), Exercise 3.3.50

Hint 1. In (a),

𝐴

has rank

1

, so

𝐴 = 𝐮 𝐯^{𝖳}

. What must

𝐮

be, and which condition on

𝐯

makes

ker 𝐴

correct?

Hint 2. In (b) and (e), count dimensions. In (c), every row has dot product

0

with every vector of the null space (Exercise 3.3.50(a)).

Sketch. (a)

𝐴 =

(1, 0, 1) {(1, - 1, 1)}^{𝖳}

. (b) None:

dim ker 𝐴 \geq 4 - 2 = 2

. (c) None:

(1, 1, 0) \cdot

(1, 0, 0) =

1 \neq

0

. (d)

𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})

. (e) None:

𝑟 = 3 - 𝑟

is impossible.

(a) Such an $𝐴$ has rank $1$ , so $𝐴 = 𝐮 𝐯^{𝖳}$ , and we may take $𝐮 = (1, 0, 1)$ (Proposition 4.3.16). Then $𝐴 𝐱 = (𝐯^{𝖳} 𝐱) 𝐮$ , so $ker 𝐴 =$ ${𝐱 | 𝐯^{𝖳} 𝐱 = 0}$ . We need $𝐯^{𝖳} (1, 1, 0) = 0$ and $𝐯^{𝖳} (0, 1, 1) = 0$ , that is, $𝑣_{1} + 𝑣_{2} = 0 = 𝑣_{2} + 𝑣_{3}$ ; take $𝐯 = (1, - 1, 1)$ . Then

𝐴 = (\begin{matrix} 1 \\ 0 \\ 1 \end{matrix}) (\begin{matrix} 1 & - 1 & 1 \end{matrix}) = (\begin{matrix} 1 & - 1 & 1 \\ 0 & 0 & 0 \\ 1 & - 1 & 1 \end{matrix}) .

Its kernel contains $(1, 1, 0)$ and $(0, 1, 1)$ , which are independent, and has dimension $3 - 1 = 2$ (Theorem 4.2.11), so it is their span; and $im 𝐴 =$ $span ((1, 0, 1))$ .

(b) None. By Theorem 4.2.11, $dim ker 𝐴 =$ $4 -$ $rank 𝐴 \geq$ $4 -$ $2 =$ $2$ , while $dim span (𝐞_{1}) = 1$ .

(c) None, over every field. By Exercise 3.3.50(a), every vector of the row space has dot product $0$ with every vector of the null space, but $(1, 1, 0) \cdot$ $(1, 0, 0) =$ $1 \neq$ $0$ .

(d) $𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ : its image is spanned by its nonzero column $𝐞_{1}$ , and $𝐴 (𝑥_{1}, 𝑥_{2}) =$ $(𝑥_{2}, 0)$ vanishes exactly when $𝑥_{2} = 0$ , so $ker 𝐴 = span (𝐞_{1})$ too.

(e) None. If $im 𝐴 = ker 𝐴$ , then $rank 𝐴 =$ $dim ker 𝐴 =$ $3 -$ $rank 𝐴$ by Theorem 4.2.11, so $2 rank 𝐴 = 3$ , which no integer satisfies. In general, a square matrix with $im 𝐴 = ker 𝐴$ must have even size.

Exercise 4.3.29.routine Let $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ . Prove or disprove.

(a)If $𝐴$ and $𝐵$ have the same four fundamental subspaces, then $𝐴 = 𝐵$ .
(b)If $𝐴$ and $𝐵$ have the same row space, then $ker 𝐴 = ker 𝐵$ .
(c)If $𝐴$ and $𝐵$ have the same column space, then $ker 𝐴^{𝖳} = ker 𝐵^{𝖳}$ .
(d)If $ker 𝐴 = ker 𝐵$ , then $im 𝐴 = im 𝐵$ .

Solution.

Uses. Exercise 3.3.50, Proposition 2.4.22 (Transpose is a linear involution), Definition 4.3.12 (The four fundamental subspaces)

Techniques. Transpose to trade rows for columns (Technique 3.2.27), Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. For (a), think of invertible matrices.

Hint 2. For (b), Exercise 3.3.50(a) describes

ker 𝐴

in terms of the row space alone. Then transpose for (c).

Hint 3. For (d), find two

2 \times 2

matrices of rank

1

with the same kernel.

Sketch. (a) False:

𝐼_{2}

and

(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})

are both invertible. (b) True:

ker 𝐴

is the set of

𝐱

with

𝐰 \cdot 𝐱 = 0

for all

𝐰

in the row space. (c) True: apply (b) to

𝐴^{𝖳}

and

𝐵^{𝖳}

, whose row spaces are

im 𝐴

and

im 𝐵

. (d) False:

(\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})

and

(\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})

(a) False. $𝐼_{2}$ and $𝐵 = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ are both invertible, so both have column space and row space $𝐹^{2}$ and null space and left null space ${𝟎}$ ; but $𝐼_{2} \neq 𝐵$ .

(b) True. By Exercise 3.3.50(a), $ker 𝐴$ is the set of $𝐱 \in 𝐹^{𝑛}$ with $𝐰 \cdot 𝐱 = 0$ for every $𝐰$ in the row space of $𝐴$ . This description involves only the row space, so equal row spaces give equal null spaces.

(c) True. The row space of $𝐴^{𝖳}$ is $im {(𝐴^{𝖳})}^{𝖳} = im 𝐴$ (Proposition 2.4.22), and likewise for $𝐵$ . So if $im 𝐴 = im 𝐵$ , then $𝐴^{𝖳}$ and $𝐵^{𝖳}$ have the same row space, and (b) gives $ker 𝐴^{𝖳} = ker 𝐵^{𝖳}$ .

(d) False. Let $𝐴 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ . Both send $(𝑥_{1}, 𝑥_{2})$ to a vector that is zero exactly when $𝑥_{1} = 0$ , so $ker 𝐴 =$ $ker 𝐵 =$ $span (𝐞_{2})$ , but $im 𝐴 = span (𝐞_{1})$ and $im 𝐵 = span (𝐞_{2})$ . Parts (b)–(d) show that the row space determines the null space and the column space determines the left null space, but that the null space does not determine the column space.

Exercise 4.3.30.standard (Sylvester’s rank inequality.) Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ .

(a)Show that $rank (𝐴 𝐵) \geq$ $rank 𝐴 +$ $rank 𝐵 -$ $𝑛$ .
(b)Deduce that if $𝐴 𝐵 = 0$ , then $rank 𝐴 + rank 𝐵 \leq 𝑛$ .
(c)Show that for $𝐴_{1},$ $\dots,$ $𝐴_{𝑘} \in$ $𝐹^{𝑛 \times 𝑛}$ ,
$rank (𝐴_{1} 𝐴_{2} \dots 𝐴_{𝑘}) \geq rank 𝐴_{1} + \dots + rank 𝐴_{𝑘} - (𝑘 - 1) 𝑛 .$
(d)Deduce that if $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ has rank $𝑛 - 1$ , then $rank (𝐴^{𝑘}) \geq 𝑛 - 𝑘$ for every $𝑘 \geq 1$ , and show by an example that equality can hold for every $𝑘 \leq 𝑛$ .

Solution.

Uses. Proposition 4.3.5 (Rank of a product, exactly), Theorem 4.2.11 (Rank–nullity), Proposition 4.1.21 (Dimensions of subspaces)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. By (4.3.1),

rank (𝐴 𝐵) =

rank 𝐵 -

dim (im 𝐵 \cap ker 𝐴)

. Bound the subtracted term.

Hint 2. For (c), induct on

𝑘

, applying (a) to

𝐴_{1} \dots 𝐴_{𝑘 - 1}

and

𝐴_{𝑘}

Hint 3. For the example in (d), take the shift

𝑁

with

𝑁 𝐞_{1} = 𝟎

and

𝑁 𝐞_{𝑗} = 𝐞_{𝑗 - 1}

Sketch. (a)

dim (im 𝐵 \cap ker 𝐴) \leq

dim ker 𝐴 =

𝑛 -

rank 𝐴

. (b) Put

rank (𝐴 𝐵) = 0

. (c) Induction:

rank (𝑃 𝐴_{𝑘}) \geq

rank 𝑃 +

rank 𝐴_{𝑘} -

𝑛

with

𝑃 = 𝐴_{1} \dots 𝐴_{𝑘 - 1}

. (d) With all

𝐴_{𝑖} = 𝐴

𝑘 (𝑛 - 1) -

(𝑘 - 1) 𝑛 =

𝑛 -

𝑘

; the shift has

rank 𝑁^{𝑘} = 𝑛 - 𝑘

(a) By (4.3.1), $rank (𝐴 𝐵) =$ $rank 𝐵 -$ $dim (im 𝐵 \cap ker 𝐴)$ . Since $im 𝐵 \cap ker 𝐴 \subseteq ker 𝐴$ , its dimension is at most $dim ker 𝐴 =$ $𝑛 -$ $rank 𝐴$ (Proposition 4.1.21(a), Theorem 4.2.11(a)). Hence

\begin{aligned} rank (𝐴 𝐵) & \geq rank 𝐵 - (𝑛 - rank 𝐴) \\ = rank 𝐴 + rank 𝐵 - 𝑛 . \end{aligned}

(b) If $𝐴 𝐵 = 0$ , then $0 =$ $rank (𝐴 𝐵) \geq$ $rank 𝐴 +$ $rank 𝐵 -$ $𝑛$ .

(c) By induction on $𝑘$ . For $𝑘 = 1$ there is nothing to prove. For $𝑘 \geq 2$ , let $𝑃 = 𝐴_{1} \dots 𝐴_{𝑘 - 1}$ . By (a), $rank (𝑃 𝐴_{𝑘}) \geq$ $rank 𝑃 +$ $rank 𝐴_{𝑘} -$ $𝑛$ , and by the induction hypothesis,

rank 𝑃 \geq rank 𝐴_{1} + \dots + rank 𝐴_{𝑘 - 1} - (𝑘 - 2) 𝑛 .

Substituting the second inequality into the first gives the claim for $𝑘$ .

(d) With $𝐴_{1} = \dots = 𝐴_{𝑘} = 𝐴$ , (c) gives $rank (𝐴^{𝑘}) \geq$ $𝑘 (𝑛 - 1) -$ $(𝑘 - 1) 𝑛 =$ $𝑛 -$ $𝑘$ . For the shift $𝑁 \in 𝐹^{𝑛 \times 𝑛}$ with $𝑁 𝐞_{1} = 𝟎$ and $𝑁 𝐞_{𝑗} = 𝐞_{𝑗 - 1}$ for $𝑗 \geq 2$ , the power $𝑁^{𝑘}$ sends $𝐞_{𝑗}$ to $𝐞_{𝑗 - 𝑘}$ for $𝑗 > 𝑘$ and to $𝟎$ for $𝑗 \leq 𝑘$ , so $im 𝑁^{𝑘} =$ $span (𝐞_{1}, \dots, 𝐞_{𝑛 - 𝑘})$ and $rank 𝑁^{𝑘} = 𝑛 - 𝑘$ for $𝑘 \leq 𝑛$ . In particular $rank 𝑁 = 𝑛 - 1$ .

Sylvester’s inequality is the lower bound that the exact formula hides: the product loses at most $dim ker 𝐴$ dimensions, because the lost directions lie in $ker 𝐴$ .

Exercise 4.3.31.hard (Frobenius’s rank inequality.) Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ , and $𝐶 \in 𝐹^{𝑝 \times 𝑞}$ .

(a)Show that
$rank (𝐴 𝐵) + rank (𝐵 𝐶) \leq rank 𝐵 + rank (𝐴 𝐵 𝐶) .$
(b)Deduce Sylvester’s inequality (Exercise 4.3.30(a)).
(c)Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ and $𝑑_{𝑘} =$ $rank (𝐴^{𝑘}) -$ $rank (𝐴^{𝑘 + 1})$ for $𝑘 \geq 0$ . Deduce from (a) that $𝑑_{0} \geq 𝑑_{1} \geq 𝑑_{2} \geq \dots$ (compare Example 4.3.6).

Solution.

Uses. Proposition 4.3.5 (Rank of a product, exactly), Proposition 2.6.15 (Kernels and images of composites), Proposition 4.1.21 (Dimensions of subspaces)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. Rewrite the inequality as

rank (𝐵 𝐶) -

rank (𝐴 (𝐵 𝐶)) \leq

rank 𝐵 -

rank (𝐴 𝐵)

: what

𝐴

destroys of

im (𝐵 𝐶)

is at most what it destroys of

im 𝐵

Hint 2. Express both sides with (4.3.1). How are

im (𝐵 𝐶)

and

im 𝐵

related?

Hint 3. For (b), take

𝐵 = 𝐼_{𝑛}

. For (c), take the three matrices

𝐴

𝐴^{𝑘}

𝐴

Sketch. By (4.3.1),

rank 𝐵 -

rank (𝐴 𝐵) =

dim (im 𝐵 \cap ker 𝐴)

and

rank (𝐵 𝐶) -

rank (𝐴 𝐵 𝐶) =

dim (im (𝐵 𝐶) \cap ker 𝐴)

. Since

im (𝐵 𝐶) \subseteq im 𝐵

, the second is at most the first. (b)

𝐵 = 𝐼_{𝑛}

. (c) With

𝐴, 𝐴^{𝑘}, 𝐴

2 rank (𝐴^{𝑘 + 1}) \leq

rank (𝐴^{𝑘}) +

rank (𝐴^{𝑘 + 2})

, which rearranges to

𝑑_{𝑘 + 1} \leq 𝑑_{𝑘}

(a) By (4.3.1), applied to $𝐴$ and $𝐵$ and to $𝐴$ and $𝐵 𝐶$ ,

\begin{aligned} rank 𝐵 - rank (𝐴 𝐵) & = dim (im 𝐵 \cap ker 𝐴), \\ rank (𝐵 𝐶) - rank (𝐴 𝐵 𝐶) & = dim (im (𝐵 𝐶) \cap ker 𝐴) . \end{aligned}

By Proposition 2.6.15(b), $im (𝐵 𝐶) \subseteq im 𝐵$ , so $im (𝐵 𝐶) \cap$ $ker 𝐴 \subseteq$ $im 𝐵 \cap$ $ker 𝐴$ , and Proposition 4.1.21(a) gives

rank (𝐵 𝐶) - rank (𝐴 𝐵 𝐶) \leq rank 𝐵 - rank (𝐴 𝐵) .

Rearranging gives (a). In words: of the directions in $im (𝐵 𝐶)$ , which is part of $im 𝐵$ , the matrix $𝐴$ can destroy no more than it destroys of all of $im 𝐵$ .

(b) Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐶 \in 𝐹^{𝑛 \times 𝑞}$ , and take $𝐵 = 𝐼_{𝑛}$ in (a): $rank 𝐴 +$ $rank 𝐶 \leq$ $rank 𝐼_{𝑛} +$ $rank (𝐴 𝐶) =$ $𝑛 +$ $rank (𝐴 𝐶)$ .

(c) Apply (a) to the three $𝑛 \times 𝑛$ matrices $𝐴$ , $𝐴^{𝑘}$ , $𝐴$ :

rank (𝐴^{𝑘 + 1}) + rank (𝐴^{𝑘 + 1}) \leq rank (𝐴^{𝑘}) + rank (𝐴^{𝑘 + 2}) .

Rearranged, $rank (𝐴^{𝑘 + 1}) -$ $rank (𝐴^{𝑘 + 2}) \leq$ $rank (𝐴^{𝑘}) -$ $rank (𝐴^{𝑘 + 1})$ , that is, $𝑑_{𝑘 + 1} \leq 𝑑_{𝑘}$ . (For $𝑘 = 0$ , $𝐴^{0} = 𝐼_{𝑛}$ .) By rank–nullity, $𝑑_{𝑘} =$ $dim ker 𝐴^{𝑘 + 1} -$ $dim ker 𝐴^{𝑘}$ , so this is Exercise 4.2.52(b) once more.

Exercise 4.3.32.hard Let $0 \leq 𝑎 \leq min (𝑚, 𝑛)$ and $0 \leq 𝑏 \leq min (𝑛, 𝑝)$ be integers. Show that there are $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ of rank $𝑎$ and $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ of rank $𝑏$ with $rank (𝐴 𝐵) = 𝑟$ if and only if

max (0, 𝑎 + 𝑏 - 𝑛) \leq 𝑟 \leq min (𝑎, 𝑏) .

For $𝑚 = 𝑛 = 𝑝 = 5$ , $𝑎 = 3$ , and $𝑏 = 4$ , list the possible values of $rank (𝐴 𝐵)$ and give a pair $𝐴$ , $𝐵$ for each.

Solution.

Uses. Theorem 4.3.3 (Rank of a product), Exercise 4.3.30, Lemma 2.4.24 (Matrix units), Proposition 2.6.18 (The column space is spanned by the columns), Corollary 1.5.17 (Sublists), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ )

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. The bounds are Theorem 4.3.3 and Sylvester’s inequality. For the converse, use matrices made of

0

s and a few

1

Hint 2. Let

𝐴

have

1

in positions

(1, 1), \dots, (𝑎, 𝑎)

and

0

elsewhere. Let

𝐵

have, in its columns

1, \dots, 𝑏

, distinct standard basis vectors

𝐞_{𝑡_{1}}, \dots, 𝐞_{𝑡_{𝑏}}

. What is

𝐴 𝐵

Hint 3.

𝐴 𝐵

keeps exactly the columns

𝐞_{𝑡_{𝑘}}

with

𝑡_{𝑘} \leq 𝑎

. How many of the

𝑡_{𝑘}

can you place in

{1, \dots, 𝑎}

Sketch. Necessity: Theorem 4.3.3 and Exercise 4.3.30(a). Sufficiency:

𝐴 =

\sum_{𝑖 \leq 𝑎} 𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}

and

𝐵 =

\sum_{𝑘 \leq 𝑏} 𝐞_{𝑡_{𝑘}} 𝐞_{𝑘}^{𝖳}

with distinct

𝑡_{𝑘}

; then

𝐴 𝐵 =

\sum_{𝑘 : 𝑡_{𝑘} \leq 𝑎} 𝐞_{𝑡_{𝑘}} 𝐞_{𝑘}^{𝖳}

has rank

| {𝑘 | 𝑡_{𝑘} \leq 𝑎} |

. Take

𝑡_{𝑘} = 𝑘

for

𝑘 \leq 𝑟

and

𝑡_{𝑘} = 𝑎 + 𝑘 - 𝑟

for

𝑟 < 𝑘 \leq 𝑏

; this needs

𝑟 \leq 𝑎

and

𝑎 + 𝑏 - 𝑟 \leq 𝑛

. For

(5; 3, 4)

𝑟 \in {2, 3}

Necessity. By Theorem 4.3.3, $rank (𝐴 𝐵) \leq$ $min (𝑎, 𝑏)$ , and by Exercise 4.3.30(a), $rank (𝐴 𝐵) \geq$ $𝑎 +$ $𝑏 -$ $𝑛$ ; ranks are nonnegative.

Sufficiency. Let $𝑟$ satisfy the bounds. A matrix whose nonzero columns are distinct standard basis vectors has rank equal to the number of those columns, since its image is spanned by them (Proposition 2.6.18), they are independent as part of the standard basis (Corollary 1.5.17), and rank is the dimension of the image (Theorem 4.2.7). Let

𝐴 = \sum_{𝑖 = 1}^{𝑎} 𝐞_{𝑖} 𝐞_{𝑖}^{𝖳} \in 𝐹^{𝑚 \times 𝑛},

whose columns are $𝐞_{1}, \dots, 𝐞_{𝑎} \in 𝐹^{𝑚}$ followed by zeros, so $rank 𝐴 = 𝑎$ . Choose distinct indices $𝑡_{1},$ $\dots,$ $𝑡_{𝑏} \in$ ${1, \dots, 𝑛}$ , specified below, and let

𝐵 = \sum_{𝑘 = 1}^{𝑏} 𝐞_{𝑡_{𝑘}} 𝐞_{𝑘}^{𝖳} \in 𝐹^{𝑛 \times 𝑝},

whose columns are $𝐞_{𝑡_{1}},$ $\dots,$ $𝐞_{𝑡_{𝑏}} \in$ $𝐹^{𝑛}$ followed by zeros, so $rank 𝐵 = 𝑏$ . By Lemma 2.4.24(c), $𝐞_{𝑖} 𝐞_{𝑖}^{𝖳} 𝐞_{𝑡_{𝑘}} 𝐞_{𝑘}^{𝖳}$ is $𝐞_{𝑖} 𝐞_{𝑘}^{𝖳}$ if $𝑡_{𝑘} = 𝑖$ and $0$ otherwise, so

𝐴 𝐵 = \sum_{𝑘 : 𝑡_{𝑘} \leq 𝑎} 𝐞_{𝑡_{𝑘}} 𝐞_{𝑘}^{𝖳},

whose nonzero columns are the distinct vectors $𝐞_{𝑡_{𝑘}}$ with $𝑡_{𝑘} \leq 𝑎$ . So $rank (𝐴 𝐵)$ is the number of $𝑘$ with $𝑡_{𝑘} \leq 𝑎$ .

Now take $𝑡_{𝑘} = 𝑘$ for $1 \leq 𝑘 \leq 𝑟$ and $𝑡_{𝑘} = 𝑎 + (𝑘 - 𝑟)$ for $𝑟 < 𝑘 \leq 𝑏$ . These are distinct, since $𝑟 \leq 𝑎$ . They lie in ${1, \dots, 𝑛}$ , since the largest is $𝑎 + 𝑏 - 𝑟 \leq 𝑛$ when $𝑟 \geq 𝑎 + 𝑏 - 𝑛$ . Exactly $𝑡_{1}, \dots, 𝑡_{𝑟}$ are at most $𝑎$ , as $𝑟 \leq 𝑏$ and $𝑡_{𝑘} > 𝑎$ for $𝑘 > 𝑟$ . So $rank (𝐴 𝐵) = 𝑟$ .

The example. With $𝑛 = 5$ , $𝑎 = 3$ , $𝑏 = 4$ : $max (0, 3 + 4 - 5) = 2$ and $min (3, 4) = 3$ , so $𝑟 \in {2, 3}$ . Take $𝐴 = (\begin{matrix} 𝐼_{3} & 0 \\ 0 & 0 \end{matrix}) \in 𝐹^{5 \times 5}$ . For $𝑟 = 3$ , take $𝑡 = (1, 2, 3, 4)$ , that is, $𝐵 = (\begin{matrix} 𝐼_{4} & 0 \\ 0 & 0 \end{matrix})$ ; then $𝐴 𝐵 = 𝐴$ has rank $3$ . For $𝑟 = 2$ , take $𝑡 = (1, 2, 4, 5)$ , that is, $𝐵$ has columns $𝐞_{1},$ $𝐞_{2},$ $𝐞_{4},$ $𝐞_{5},$ $𝟎$ ; then $𝐴 𝐵$ has columns $𝐞_{1}, 𝐞_{2}, 𝟎, 𝟎, 𝟎$ , of rank $2$ .

Exercise 4.3.33.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ .

(a)Show that, over any field, $rank (𝐴^{𝖳} 𝐴) =$ $rank 𝐴 -$ $dim (im 𝐴 \cap ker 𝐴^{𝖳})$ .
(b)Let $𝐹 = ℝ$ . Show that $im 𝐴 \cap ker 𝐴^{𝖳} = {𝟎}$ , and deduce that $rank (𝐴^{𝖳} 𝐴) =$ $rank 𝐴$ .
(c)Let $𝐹 = ℝ$ . Without using Theorem 4.3.8, deduce from (b) that $rank 𝐴^{𝖳} = rank 𝐴$ and $rank (𝐴 𝐴^{𝖳}) =$ $rank 𝐴$ .

Solution.

Uses. Proposition 4.3.5 (Rank of a product, exactly), Theorem 4.3.3 (Rank of a product), Proposition 2.4.23 (Transpose of a product), Proposition 2.4.22 (Transpose is a linear involution)

Techniques. A sum of nonnegative terms (Technique 6.1.9)

Hint 1. (a) is (4.3.1) for the product

𝐴^{𝖳} 𝐴

Hint 2. For (b), if

𝐲 = 𝐴 𝐱

and

𝐴^{𝖳} 𝐲 = 𝟎

, compute

𝐲^{𝖳} 𝐲

in two ways.

Hint 3. For (c),

rank 𝐴 =

rank (𝐴^{𝖳} 𝐴) \leq

rank 𝐴^{𝖳}

. Now apply the same to

𝐴^{𝖳}

Sketch. (a) is (4.3.1). (b) If

𝐲 = 𝐴 𝐱 \in ker 𝐴^{𝖳}

, then

\sum_{𝑖} 𝑦_{𝑖}^{2} =

𝐲^{𝖳} 𝐲 =

𝐱^{𝖳} 𝐴^{𝖳} 𝐲 =

0

, so

𝐲 = 𝟎

. (c)

rank 𝐴 =

rank (𝐴^{𝖳} 𝐴) \leq

rank 𝐴^{𝖳}

by Theorem 4.3.3, and the same for

𝐴^{𝖳}

gives the reverse; then

rank (𝐴 𝐴^{𝖳}) =

rank ({(𝐴^{𝖳})}^{𝖳} 𝐴^{𝖳}) =

rank 𝐴^{𝖳} =

rank 𝐴

(a) This is (4.3.1) with $𝐴^{𝖳}$ in the role of $𝐴$ and $𝐴$ in the role of $𝐵$ .

(b) Let $𝐲 \in im 𝐴 \cap ker 𝐴^{𝖳}$ , say $𝐲 = 𝐴 𝐱$ with $𝐴^{𝖳} 𝐲 = 𝟎$ . By Proposition 2.4.23, $𝐲^{𝖳} = 𝐱^{𝖳} 𝐴^{𝖳}$ , so

𝑦_{1}^{2} + \dots + 𝑦_{𝑚}^{2} = 𝐲^{𝖳} 𝐲 = 𝐱^{𝖳} (𝐴^{𝖳} 𝐲) = 𝐱^{𝖳} 𝟎 = 0 .

A sum of squares of real numbers is $0$ only if every term is $0$ (Technique 6.1.9), so $𝐲 = 𝟎$ . By (a), $rank (𝐴^{𝖳} 𝐴) =$ $rank 𝐴$ .

(c) By (b) and Theorem 4.3.3, $rank 𝐴 =$ $rank (𝐴^{𝖳} 𝐴) \leq$ $rank 𝐴^{𝖳}$ . Applying this to the real matrix $𝐴^{𝖳}$ , whose transpose is $𝐴$ (Proposition 2.4.22), gives $rank 𝐴^{𝖳} \leq rank 𝐴$ . So $rank 𝐴^{𝖳} = rank 𝐴$ . Finally, (b) for $𝐴^{𝖳}$ gives $rank (𝐴 𝐴^{𝖳}) =$ $rank ({(𝐴^{𝖳})}^{𝖳} 𝐴^{𝖳}) =$ $rank 𝐴^{𝖳} =$ $rank 𝐴$ .

Over $ℂ$ the same argument works with the conjugate transpose $𝐴^{*}$ in place of $𝐴^{𝖳}$ , since $𝑦_{1} 𝑦_{1} +$ $\dots +$ $𝑦_{𝑚} 𝑦_{𝑚} =$ ${| 𝑦_{1} |}^{2} +$ $\dots +$ ${| 𝑦_{𝑚} |}^{2}$ ; this is Proposition 6.5.9. Exercise 4.3.34 shows what goes wrong with $𝐴^{𝖳}$ .

Exercise 4.3.34.standard Prove or disprove.

(a)Over $𝔽_{2}$ , $rank (𝐴^{𝖳} 𝐴) =$ $rank 𝐴$ for every matrix $𝐴$ .
(b)Over $ℂ$ , $rank (𝐴^{𝖳} 𝐴) =$ $rank 𝐴$ for every matrix $𝐴$ .
(c)Over $ℚ$ , $rank (𝐴^{𝖳} 𝐴) =$ $rank 𝐴$ for every matrix $𝐴$ .
(d)Over $𝔽_{2}$ , if the columns of $𝐴$ are linearly independent, then $𝐴^{𝖳} 𝐴$ is invertible.

Which step of Exercise 4.3.33(b) fails in the false cases?

Solution.

Uses. Exercise 4.3.33, Exercise 3.3.54, Corollary 3.5.25 (The invertible matrix theorem)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Look for a nonzero vector

𝐲

with

𝑦_{1}^{2} + \dots + 𝑦_{𝑚}^{2} = 0

, and use it as a one-column matrix.

Hint 2. For (c), a rational matrix is a real matrix, and its rank does not depend on which of the two fields we compute in.

Sketch. (a) False:

𝐴 = {(1, 1)}^{𝖳}

gives

𝐴^{𝖳} 𝐴 = 1 + 1 = 0

. (b) False:

𝐴 = {(1, 𝑖)}^{𝖳}

gives

1 + 𝑖^{2} = 0

. (c) True, by Exercise 4.3.33 and Exercise 3.3.54. (d) False:

𝐴 = (\begin{matrix} 1 & 0 \\ 1 & 0 \\ 0 & 1 \end{matrix})

gives

𝐴^{𝖳} 𝐴 = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix})

. The failing step is “a sum of squares is

0

only if each term is

0

”.

(a) False. Let $𝐴 = (\begin{matrix} 1 \\ 1 \end{matrix}) \in 𝔽_{2}^{2 \times 1}$ , of rank $1$ . Then $𝐴^{𝖳} 𝐴 =$ $(1 \cdot 1 + 1 \cdot 1) =$ $(0)$ , of rank $0$ .

(b) False. Let $𝐴 = (\begin{matrix} 1 \\ 𝑖 \end{matrix}) \in ℂ^{2 \times 1}$ , of rank $1$ . Then $𝐴^{𝖳} 𝐴 =$ $(1 + 𝑖^{2}) =$ $(0)$ .

(c) True. A matrix with rational entries is also a real matrix, and by Exercise 3.3.54(a) its reduced row echelon form, hence its rank, is the same over $ℚ$ and over $ℝ$ . The same holds for $𝐴^{𝖳} 𝐴$ , which also has rational entries. So $rank (𝐴^{𝖳} 𝐴) =$ $rank 𝐴$ over $ℚ$ follows from Exercise 4.3.33(b) over $ℝ$ .

(d) False. Over $𝔽_{2}$ , let $𝐴 = (\begin{matrix} 1 & 0 \\ 1 & 0 \\ 0 & 1 \end{matrix})$ , whose two columns are independent. Then

𝐴^{𝖳} 𝐴 = (\begin{matrix} 1 + 1 & 0 \\ 0 & 1 \end{matrix}) = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}),

which has rank $1$ and is not invertible (Corollary 3.5.25).

In each false case, the vector $𝐲 = 𝐴 𝐞_{1}$ , that is, $(1, 1)$ , $(1, 𝑖)$ , or $(1, 1, 0)$ , is nonzero, satisfies $𝐲^{𝖳} 𝐲 = 0$ , and lies in $im 𝐴 \cap ker 𝐴^{𝖳}$ , which is exactly what Exercise 4.3.33(a) says must happen when the rank drops. The proof of Exercise 4.3.33(b) used that a sum of squares vanishes only when every term does, which is a property of $ℝ$ (and of its subfields), not of fields in general.

Exercise 4.3.35.standard Find the error in the following argument. Is its conclusion true? Give a matrix for which the false step fails, and repair the argument.

Claim. For every $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , $rank 𝐴^{𝖳} = rank 𝐴$ .

Proof. Let $𝐴_{𝑟} = rref (𝐴)$ , with $𝑟$ pivots. Row operations do not change the column space, so $im 𝐴 = im 𝐴_{𝑟}$ . The columns of $𝐴_{𝑟}$ lie in $span (𝐞_{1}, \dots, 𝐞_{𝑟})$ and include $𝐞_{1}, \dots, 𝐞_{𝑟}$ , so $im 𝐴 =$ $span (𝐞_{1}, \dots, 𝐞_{𝑟})$ , and $rank 𝐴 = 𝑟$ . Row operations do not change the row space either, and the $𝑟$ nonzero rows of $𝐴_{𝑟}$ are linearly independent, so $rank 𝐴^{𝖳} = 𝑟$ as well.

Solution.

Uses. Non-example 4.2.8 (The columns of $𝐴_{𝑟}$ are the wrong vectors), Proposition 4.3.1 (Invertible factors preserve rank), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ )

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Which operations preserve the column space: row operations or column operations?

Hint 2. Try

𝐴 = (\begin{matrix} 1 & 2 \\ 2 & 4 \end{matrix})

Hint 3. The conclusion

rank 𝐴 = 𝑟

is still right. Why do

im 𝐴

and

im 𝐴_{𝑟}

have the same dimension even though they are different?

Sketch. The false step is

im 𝐴 = im 𝐴_{𝑟}

: row operations preserve the row space and the relations among the columns, not the column space. For

𝐴 = (\begin{matrix} 1 & 2 \\ 2 & 4 \end{matrix})

im 𝐴 = span ((1, 2))

but

im 𝐴_{𝑟} = span (𝐞_{1})

. The claim is true. Repair:

𝐴 = 𝐺^{- 1} 𝐴_{𝑟}

, so

rank 𝐴 =

rank 𝐴_{𝑟} =

𝑟

by Proposition 4.3.1(a) (or directly by Theorem 4.2.7); the rest of the argument is the second proof of Theorem 4.3.8.

The error. The step “row operations do not change the column space” is false. Row operations preserve the row space and the linear relations among the columns, but they move the columns themselves. For $𝐴 = (\begin{matrix} 1 & 2 \\ 2 & 4 \end{matrix})$ we have $𝐴_{𝑟} = (\begin{matrix} 1 & 2 \\ 0 & 0 \end{matrix})$ , so $im 𝐴 = span ((1, 2))$ while $im 𝐴_{𝑟} = span (𝐞_{1})$ (Non-example 4.2.8). In particular the intermediate conclusion $im 𝐴 =$ $span (𝐞_{1}, \dots, 𝐞_{𝑟})$ is false for this $𝐴$ .

The conclusion. The claim is true; it is Theorem 4.3.8. Only the first half of the argument needs repair. With $𝐺$ invertible and $𝐺 𝐴 = 𝐴_{𝑟}$ , Proposition 4.3.1(a) gives $rank 𝐴 =$ $rank (𝐺 𝐴) =$ $rank 𝐴_{𝑟} =$ $𝑟$ , although $im 𝐴 \neq im 𝐴_{𝑟}$ in general. (This is also the definition of $rank 𝐴$ as the number of pivots, together with Theorem 4.2.7.) The second half is correct as stated: $𝐴$ and $𝐴_{𝑟}$ have the same row space, and the nonzero rows of $𝐴_{𝑟}$ are independent. It is the second proof of Theorem 4.3.8.

The two halves are not symmetric: row operations keep the row space as a set, but keep the column space only up to an invertible map, so only its dimension survives.

Exercise 4.3.36.standard Prove or disprove. All matrices are over a field $𝐹$ .

(a) $rank (𝐴 𝐵) =$ $rank (𝐵 𝐴)$ for all $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ .
(b)If $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ both have rank $𝑛$ , then $rank (𝐴 𝐵) = 𝑛$ .
(c)If $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ and $im 𝐴 \cap im 𝐵 = {𝟎}$ , then $rank (𝐴 + 𝐵) =$ $rank 𝐴 +$ $rank 𝐵$ .
(d)If $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ and $rank (𝐴^{2}) = rank 𝐴$ , then $rank (𝐴^{𝑘}) = rank 𝐴$ for every $𝑘 \geq 1$ .

Solution.

Uses. Proposition 4.3.5 (Rank of a product, exactly), Theorem 4.2.11 (Rank–nullity), Proposition 2.6.15 (Kernels and images of composites), Example 4.3.4 (A product of rank zero)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. For (a), see Example 4.3.4.

Hint 2. For (b), what are

ker 𝐴

and

im 𝐵

when both ranks are

𝑛

Hint 3. For (c), the columns may avoid each other while the rows do not. Try

2 \times 2

matrices with a single nonzero entry each, in the same column.

Hint 4. For (d), use (4.3.1) with

𝐴^{𝑘}

and

𝐴

: the loss is

dim (im 𝐴^{𝑘} \cap ker 𝐴)

Sketch. (a) False:

𝑀 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})

𝑁 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})

give

𝑀 𝑁 = 𝑁

𝑁 𝑀 = 0

. (b) True:

ker 𝐴 = {𝟎}

, so

rank (𝐴 𝐵) =

rank 𝐵 =

𝑛

. (c) False:

(\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) +

(\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}) =

(\begin{matrix} 1 & 0 \\ 1 & 0 \end{matrix})

has rank

1

. (d) True:

im 𝐴 \cap ker 𝐴 = {𝟎}

, and

im 𝐴^{𝑘} \subseteq im 𝐴

, so

rank (𝐴^{𝑘 + 1}) =

rank (𝐴^{𝑘}) -

dim (im 𝐴^{𝑘} \cap ker 𝐴) =

rank (𝐴^{𝑘})

(a) False. With $𝑀 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ and $𝑁 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ , we have $𝑀 𝑁 = 𝑁$ , of rank $1$ , and $𝑁 𝑀 = 0$ (Example 4.3.4).

(b) True. $𝐴$ has $𝑛$ columns and rank $𝑛$ , so $dim ker 𝐴 = 0$ (Theorem 4.2.11). By (4.3.1), $rank (𝐴 𝐵) =$ $rank 𝐵 -$ $dim (im 𝐵 \cap ker 𝐴) =$ $𝑛 -$ $0 =$ $𝑛$ .

(c) False. Let $𝐴 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ . Then $im 𝐴 = span (𝐞_{1})$ and $im 𝐵 = span (𝐞_{2})$ meet only in $𝟎$ , but $𝐴 + 𝐵 = (\begin{matrix} 1 & 0 \\ 1 & 0 \end{matrix})$ has rank $1 < 2$ . Here the row spaces coincide. (If both $im 𝐴 \cap im 𝐵 = {𝟎}$ and $im 𝐴^{𝖳} \cap$ $im 𝐵^{𝖳} =$ ${𝟎}$ , then the equality does hold, but that needs more work.)

(d) True. By (4.3.1) with $𝐵 = 𝐴$ , the hypothesis says $im 𝐴 \cap ker 𝐴 = {𝟎}$ . For $𝑘 \geq 1$ , (4.3.1) applied to $𝐴$ and $𝐴^{𝑘}$ gives

rank (𝐴^{𝑘 + 1}) = rank (𝐴^{𝑘}) - dim (im 𝐴^{𝑘} \cap ker 𝐴) .

Since $𝐴^{𝑘} = 𝐴 \circ 𝐴^{𝑘 - 1}$ as maps, $im 𝐴^{𝑘} \subseteq im 𝐴$ (Proposition 2.6.15(b)), so $im 𝐴^{𝑘} \cap$ $ker 𝐴 \subseteq$ $im 𝐴 \cap$ $ker 𝐴 =$ ${𝟎}$ , and $rank (𝐴^{𝑘 + 1}) =$ $rank (𝐴^{𝑘})$ . By induction, $rank (𝐴^{𝑘}) = rank 𝐴$ for all $𝑘 \geq 1$ .

Exercise 4.3.37.standard Let $𝐮, 𝐯 \in 𝐹^{𝑛}$ , and let $𝑠 = 𝐯^{𝖳} 𝐮$ .

(a)Show that if $1 + 𝑠 \neq 0$ , then $𝐼_{𝑛} + 𝐮 𝐯^{𝖳}$ is invertible, with
${(𝐼_{𝑛} + 𝐮 𝐯^{𝖳})}^{- 1} = 𝐼_{𝑛} - \frac{1}{1 + 𝑠} 𝐮 𝐯^{𝖳} .$
(b)Show that if $1 + 𝑠 = 0$ , then $𝐼_{𝑛} + 𝐮 𝐯^{𝖳}$ is not invertible, and that its rank is $𝑛 - 1$ .
(c)Let $𝐽 \in 𝐹^{𝑛 \times 𝑛}$ have every entry equal to $1$ . For which $𝑐 \in 𝐹$ is $𝐼_{𝑛} + 𝑐 𝐽$ invertible, and what is its inverse? Is $𝐼_{4} + 𝐽$ invertible over $ℚ$ ? Over $𝔽_{5}$ ?

Solution.

Uses. Theorem 3.5.23 (One-sided inverses of square matrices), Proposition 4.3.20 (Rank is subadditive), Proposition 4.3.16 (Rank-one matrices), Corollary 3.5.25 (The invertible matrix theorem)

Techniques. Write a rank-one matrix as $𝐮 𝐯^{𝖳}$ (Technique 4.3.17), Guess the inverse, then check both products (Technique 2.5.16)

Hint 1. Multiply out, using

𝐮 𝐯^{𝖳} 𝐮 𝐯^{𝖳} =

𝑠 𝐮 𝐯^{𝖳}

Hint 2. For (b), apply

𝐼_{𝑛} + 𝐮 𝐯^{𝖳}

𝐮

. For the rank, compare

𝐼_{𝑛}

with

(𝐼_{𝑛} + 𝐮 𝐯^{𝖳}) -

𝐮 𝐯^{𝖳}

Hint 3.

𝐽 = 𝟏 𝟏^{𝖳}

, where

𝟏

is the vector of ones.

Sketch. (a)

(𝐼 + 𝐮 𝐯^{𝖳}) (𝐼 - {(1 + 𝑠)}^{- 1} 𝐮 𝐯^{𝖳}) =

𝐼 +

𝐮 𝐯^{𝖳} -

{(1 + 𝑠)}^{- 1} (1 + 𝑠) 𝐮 𝐯^{𝖳} =

𝐼

. (b)

(𝐼 + 𝐮 𝐯^{𝖳}) 𝐮 =

(1 + 𝑠) 𝐮 =

𝟎

with

𝐮 \neq 𝟎

; and

𝑛 =

rank 𝐼 \leq

rank (𝐼 + 𝐮 𝐯^{𝖳}) +

1

. (c)

𝑐 𝐽 = (𝑐 𝟏) 𝟏^{𝖳}

𝑠 = 𝑐 𝑛

: invertible iff

1 + 𝑐 𝑛 \neq 0

, inverse

𝐼 - 𝑐 {(1 + 𝑐 𝑛)}^{- 1} 𝐽

𝐼_{4} + 𝐽

: invertible over

ℚ

(inverse

𝐼 - 𝐽 / 5

), not over

𝔽_{5}

(a) Let $𝑁 = 𝐮 𝐯^{𝖳}$ . Then $𝑁^{2} =$ $𝐮 (𝐯^{𝖳} 𝐮) 𝐯^{𝖳} =$ $𝑠 𝑁$ (Technique 4.3.17), so

\begin{aligned} (𝐼_{𝑛} + 𝑁) (𝐼_{𝑛} - {(1 + 𝑠)}^{- 1} 𝑁) & = 𝐼_{𝑛} + 𝑁 - {(1 + 𝑠)}^{- 1} (𝑁 + 𝑠 𝑁) \\ = 𝐼_{𝑛} + 𝑁 - 𝑁 = 𝐼_{𝑛} . \end{aligned}

A one-sided inverse of a square matrix is two-sided (Theorem 3.5.23), so $𝐼_{𝑛} + 𝑁$ is invertible with the stated inverse.

(b) Suppose $1 + 𝑠 = 0$ . Then $𝐮 \neq 𝟎$ , since otherwise $𝑠 = 0$ . Now $(𝐼_{𝑛} + 𝑁) 𝐮 =$ $𝐮 +$ $𝐮 (𝐯^{𝖳} 𝐮) =$ $(1 + 𝑠) 𝐮 =$ $𝟎$ , so $𝐼_{𝑛} + 𝑁$ has a nonzero vector in its kernel and is not invertible (Corollary 3.5.25). Its rank is at most $𝑛 - 1$ . Also $𝐯 \neq 𝟎$ , since $𝐯^{𝖳} 𝐮 = - 1$ , so $𝑁$ has rank one (Proposition 4.3.16), and by Proposition 4.3.20,

\begin{aligned} 𝑛 = rank 𝐼_{𝑛} & = rank ((𝐼_{𝑛} + 𝑁) + (- 𝑁)) \\ \leq rank (𝐼_{𝑛} + 𝑁) + 1 . \end{aligned}

So $rank (𝐼_{𝑛} + 𝑁) =$ $𝑛 -$ $1$ .

(c) $𝐽 = 𝟏 𝟏^{𝖳}$ , so $𝑐 𝐽 = 𝐮 𝐯^{𝖳}$ with $𝐮 = 𝑐 𝟏$ and $𝐯 = 𝟏$ , and $𝑠 =$ $𝟏^{𝖳} (𝑐 𝟏) =$ $𝑐 𝑛$ , where $𝑛$ means $𝑛 \cdot 1 \in 𝐹$ . By (a) and (b), $𝐼_{𝑛} + 𝑐 𝐽$ is invertible if and only if $1 + 𝑐 𝑛 \neq 0$ , and then

{(𝐼_{𝑛} + 𝑐 𝐽)}^{- 1} = 𝐼_{𝑛} - \frac{𝑐}{1 + 𝑐 𝑛} 𝐽 .

For $𝐼_{4} + 𝐽$ , $𝑐 = 1$ and $1 + 𝑐 𝑛 = 5$ . Over $ℚ$ , $5 \neq 0$ , so ${(𝐼_{4} + 𝐽)}^{- 1} =$ $𝐼_{4} -$ $𝐽 / 5$ . Over $𝔽_{5}$ , $5 = 0$ , so $𝐼_{4} + 𝐽$ is not invertible, and indeed $(𝐼_{4} + 𝐽) 𝟏 =$ $𝟏 +$ $4 𝟏 =$ $5 𝟏 =$ $𝟎$ .

Exercise 4.3.38.standard Let

𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}

and suppose that

rank (𝐴 𝐵 - 𝐵 𝐴) = 1

. Show that

{(𝐴 𝐵 - 𝐵 𝐴)}^{2} = 0

. Give an example in which

rank (𝐴 𝐵 - 𝐵 𝐴) = 1

Solution.

Uses. Proposition 4.3.16 (Rank-one matrices), Example 4.3.18 (Powers of a rank-one matrix), Proposition 2.4.28 (Cyclicity of the trace), Proposition 2.4.27 (The trace is linear)

Techniques. Write a rank-one matrix as $𝐮 𝐯^{𝖳}$ (Technique 4.3.17), Cyclicity of trace (Technique 2.4.29)

Hint 1. A rank-one matrix

𝑋

satisfies

𝑋^{2} = (tr 𝑋) 𝑋

Hint 2. What is the trace of a commutator?

Sketch.

𝑋 = 𝐴 𝐵 - 𝐵 𝐴

has rank one, so

𝑋^{2} = (tr 𝑋) 𝑋

by Example 4.3.18, and

tr 𝑋 =

tr (𝐴 𝐵) -

tr (𝐵 𝐴) =

0

. Example:

𝐴 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})

𝐵 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})

𝐴 𝐵 - 𝐵 𝐴 = 𝐵

Let $𝑋 = 𝐴 𝐵 - 𝐵 𝐴$ . Since $rank 𝑋 = 1$ , Example 4.3.18 gives $𝑋^{2} = (tr 𝑋) 𝑋$ . By linearity and cyclicity of the trace (Proposition 2.4.27, Proposition 2.4.28), $tr 𝑋 =$ $tr (𝐴 𝐵) -$ $tr (𝐵 𝐴) =$ $0$ . Hence $𝑋^{2} = 0$ .

For an example, let $𝐴 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ . Then $𝐴 𝐵 = 𝐵$ and $𝐵 𝐴 = 0$ , so $𝐴 𝐵 - 𝐵 𝐴 = 𝐵$ , which has rank $1$ , and indeed $𝐵^{2} = 0$ .

The hypothesis cannot be weakened to $rank (𝐴 𝐵 - 𝐵 𝐴) \leq 2$ : with $𝐴 = 𝐞_{1} 𝐞_{2}^{𝖳}$ and $𝐵 = 𝐞_{2} 𝐞_{1}^{𝖳}$ in $𝐹^{2 \times 2}$ , $𝐴 𝐵 - 𝐵 𝐴 = (\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix})$ , which has rank $2$ and square $𝐼_{2}$ over every field.

Exercise 4.3.39.routine

(a)Show that $rank (𝐴 + 𝐵) \geq$ $| rank 𝐴 -$ $rank 𝐵 |$ for $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ .
(b)Show that changing one entry of a matrix changes its rank by at most $1$ .
(c)Let $𝑀_{𝑡} \in ℝ^{5 \times 5}$ have every diagonal entry equal to $1$ and every other entry equal to $𝑡$ . Show that $rank 𝑀_{𝑡} \geq 4$ for every $𝑡 \neq 1$ .

Solution.

Uses. Proposition 4.3.20 (Rank is subadditive), Proposition 4.3.16 (Rank-one matrices), Lemma 2.4.24 (Matrix units), Proposition 4.3.1 (Invertible factors preserve rank)

Techniques. Write a rank-one matrix as $𝐮 𝐯^{𝖳}$ (Technique 4.3.17)

Hint 1. Write

𝐴 = (𝐴 + 𝐵) + (- 𝐵)

and apply subadditivity.

Hint 2. Changing entry

(𝑖, 𝑗)

𝑐

adds

𝑐 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}

Hint 3.

𝑀_{𝑡} =

(1 - 𝑡) 𝐼_{5} +

𝑡 𝐽

, where

𝐽

is the all-ones matrix, of rank one.

Sketch. (a)

rank 𝐴 \leq

rank (𝐴 + 𝐵) +

rank (- 𝐵)

and symmetrically. (b) The change adds

𝑐 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}

, of rank at most

1

; apply (a). (c)

𝑀_{𝑡} =

(1 - 𝑡) 𝐼_{5} +

𝑡 𝐽

; for

𝑡 \neq 1

(1 - 𝑡) 𝐼_{5}

has rank

5

and

𝑡 𝐽

rank at most

1

, so

rank 𝑀_{𝑡} \geq 4

(a) $- 𝐵$ has the same image as $𝐵$ , so $rank (- 𝐵) = rank 𝐵$ . By Proposition 4.3.20, $rank 𝐴 =$ $rank ((𝐴 + 𝐵) + (- 𝐵)) \leq$ $rank (𝐴 + 𝐵) +$ $rank 𝐵$ , so $rank (𝐴 + 𝐵) \geq$ $rank 𝐴 -$ $rank 𝐵$ . Exchanging $𝐴$ and $𝐵$ gives $rank (𝐴 + 𝐵) \geq$ $rank 𝐵 -$ $rank 𝐴$ .

(b) Changing entry $(𝑖, 𝑗)$ of $𝐴$ from $𝑎_{𝑖 𝑗}$ to $𝑎_{𝑖 𝑗} + 𝑐$ replaces $𝐴$ by $𝐴^{'} =$ $𝐴 +$ $𝑐 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}$ (Lemma 2.4.24). The matrix $𝑐 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}$ has rank $0$ (if $𝑐 = 0$ ) or $1$ (Proposition 4.3.16). By (a) and Proposition 4.3.20, $rank 𝐴 -$ $1 \leq$ $rank 𝐴^{'} \leq$ $rank 𝐴 +$ $1$ .

(c) Let $𝐽$ be the all-ones matrix, $𝐽 = 𝟏 𝟏^{𝖳}$ , of rank $1$ . Then $𝑀_{𝑡} =$ $(1 - 𝑡) 𝐼_{5} +$ $𝑡 𝐽$ . For $𝑡 \neq 1$ , $(1 - 𝑡) 𝐼_{5}$ is invertible, of rank $5$ , and $rank (𝑡 𝐽) \leq 1$ , so by (a), $rank 𝑀_{𝑡} \geq 5 - 1 = 4$ . (For $𝑡 = 1$ , $𝑀_{1} = 𝐽$ has rank $1$ . By Exercise 4.3.37(c), applied to $𝐼_{5} + (𝑡 / (1 - 𝑡)) 𝐽$ , the rank is exactly $4$ only for $𝑡 = - 1 / 4$ .)

Exercise 4.3.40.hard Let $𝑛 \geq 3$ , and let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ have entries $𝑎_{𝑖 𝑗} = {(𝑖 - 𝑗)}^{2}$ , read as elements of $𝐹$ .

(a)Show that $rank 𝐴 \leq 3$ over every field, by writing $𝐴$ as a sum of three matrices of rank at most one.
(b)Show that $rank 𝐴 = 3$ if $1 + 1 \neq 0$ in $𝐹$ .
(c)Find $rank 𝐴$ over $𝔽_{2}$ .

Solution.

Uses. Proposition 4.3.20 (Rank is subadditive), Proposition 4.3.16 (Rank-one matrices), Proposition 4.3.1 (Invertible factors preserve rank), Theorem 4.3.8 (Row rank equals column rank), Theorem 3.5.13 (Second Fundamental Theorem, completed), Proposition 2.6.15 (Kernels and images of composites), Theorem 3.4.24 (Polynomial interpolation), Corollary 3.5.16 (Lists of vectors in $𝐹^{𝑚}$ ), Theorem 2.4.34 (Block multiplication)

Techniques. Write a rank-one matrix as $𝐮 𝐯^{𝖳}$ (Technique 4.3.17)

Hint 1.

{(𝑖 - 𝑗)}^{2} =

𝑖^{2} -

2 𝑖 𝑗 +

𝑗^{2}

. Let

𝟏

𝐰

𝐪

be the vectors with entries

1

𝑖

𝑖^{2}

Hint 2. Write

𝐴 = 𝑋 𝑀 𝑋^{𝖳}

with

𝑋 =

(\begin{matrix} 𝟏 & 𝐰 & 𝐪 \end{matrix}) \in

𝐹^{𝑛 \times 3}

and a

3 \times 3

matrix

𝑀

. When is

𝑀

invertible, and when are the columns of

𝑋

independent?

Hint 3. Over

𝔽_{2}

- 2 = 0

and

𝑖^{2} = 𝑖

Sketch. (a)

𝐴 =

𝐪 𝟏^{𝖳} -

2 𝐰 𝐰^{𝖳} +

𝟏 𝐪^{𝖳}

. (b)

𝐴 = 𝑋 𝑀 𝑋^{𝖳}

with

𝑀 = (\begin{matrix} 0 & 0 & 1 \\ 0 & - 2 & 0 \\ 1 & 0 & 0 \end{matrix})

, invertible when

2 \neq 0

. Rows

1, 2, 3

𝑋

form the Vandermonde matrix for the distinct nodes

1, 2, 3

, so

rank 𝑋 = 3

, and

𝑇_{𝑋^{𝖳}}

is onto

𝐹^{3}

. Hence

im 𝐴 =

im (𝑋 𝑀) =

im 𝑋

, of dimension

3

. (c) Over

𝔽_{2}

𝑎_{𝑖 𝑗} = 𝑖 + 𝑗

, so

𝐴 = 𝐰 𝟏^{𝖳} + 𝟏 𝐰^{𝖳}

has rank

2

Let $𝟏, 𝐰, 𝐪 \in 𝐹^{𝑛}$ have entries $1$ , $𝑖$ , and $𝑖^{2}$ in position $𝑖$ .

(a) Since ${(𝑖 - 𝑗)}^{2} =$ $𝑖^{2} \cdot$ $1 -$ $2 𝑖 𝑗 +$ $1 \cdot$ $𝑗^{2}$ , entry by entry

𝐴 = 𝐪 𝟏^{𝖳} - 2 𝐰 𝐰^{𝖳} + 𝟏 𝐪^{𝖳} .

Each term has rank at most one (Proposition 4.3.16), so $rank 𝐴 \leq 3$ by Proposition 4.3.20.

(b) Let $𝑋 =$ $(\begin{matrix} 𝟏 & 𝐰 & 𝐪 \end{matrix}) \in$ $𝐹^{𝑛 \times 3}$ and $𝑀 = (\begin{matrix} 0 & 0 & 1 \\ 0 & - 2 & 0 \\ 1 & 0 & 0 \end{matrix})$ . By block multiplication (Theorem 2.4.34), $𝑋 𝑀 𝑋^{𝖳} =$ $𝐪 𝟏^{𝖳} -$ $2 𝐰 𝐰^{𝖳} +$ $𝟏 𝐪^{𝖳} =$ $𝐴$ . Suppose $2 \neq 0$ in $𝐹$ .

$𝑀$ is invertible. $𝑀^{2} = (\begin{matrix} 1 & 0 & 0 \\ 0 & 4 & 0 \\ 0 & 0 & 1 \end{matrix})$ , which is invertible since $4 \neq 0$ ; so $𝑀$ has the inverse $𝑀 {(𝑀^{2})}^{- 1}$ .

$rank 𝑋 = 3$ . The nodes $1, 2, 3$ of $𝐹$ are distinct, since their differences are $1$ and $2$ , both nonzero. The first three rows of $𝑋$ form the matrix $(\begin{matrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{matrix})$ , which is invertible by Theorem 3.4.24, so its columns are independent. A relation among the columns of $𝑋$ restricts to a relation among the columns of this $3 \times 3$ matrix, so the columns of $𝑋$ are independent, and $rank 𝑋 = 3$ (Corollary 3.5.16(a)).

Conclusion. By Theorem 4.3.8, $rank 𝑋^{𝖳} = 3$ , so $𝑇_{𝑋^{𝖳}} : 𝐹^{𝑛} \to 𝐹^{3}$ is surjective. Hence $im 𝐴 =$ $im (𝑋 𝑀 𝑋^{𝖳}) =$ $im (𝑋 𝑀)$ (Proposition 2.6.15(b)), and $rank (𝑋 𝑀) =$ $rank 𝑋 =$ $3$ (Proposition 4.3.1). So $rank 𝐴 = 3$ .

(c) Over $𝔽_{2}$ , $- 2 = 0$ , and $𝑖^{2}$ has the same parity as $𝑖$ , so $𝐪 = 𝐰$ and $𝑎_{𝑖 𝑗} = 𝑖 + 𝑗$ . So $𝐴 = 𝐰 𝟏^{𝖳} + 𝟏 𝐰^{𝖳}$ has rank at most $2$ . Rows $1$ and $2$ are $(0, 1, 0, 1, \dots)$ and $(1, 0, 1, 0, \dots)$ , which are independent, so $rank 𝐴 \geq 2$ by Theorem 4.3.8. Hence $rank 𝐴 = 2$ over $𝔽_{2}$ .

Exercise 4.3.41.standard

(a)Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ . Show that $rank 𝐴 \leq 1$ if and only if $𝑎_{𝑖 𝑗} 𝑎_{𝑘 𝑙} =$ $𝑎_{𝑖 𝑙} 𝑎_{𝑘 𝑗}$ for all $𝑖, 𝑘 \in {1, \dots, 𝑚}$ and $𝑗, 𝑙 \in {1, \dots, 𝑛}$ .
(b)Find all $𝑡 \in ℝ$ for which $(\begin{matrix} 1 & 𝑡 & 2 \\ 𝑡 & 4 & 2 𝑡 \end{matrix})$ has rank $1$ .

Solution.

Uses. Proposition 4.3.16 (Rank-one matrices)

Techniques. Write a rank-one matrix as $𝐮 𝐯^{𝖳}$ (Technique 4.3.17)

Hint 1. For “only if”, write

𝐴 = 𝐮 𝐯^{𝖳}

, so

𝑎_{𝑖 𝑗} = 𝑢_{𝑖} 𝑣_{𝑗}

Hint 2. For “if”, assume

𝐴 \neq 0

and fix an entry

𝑎_{𝑘 𝑙} \neq 0

. Solve the condition for

𝑎_{𝑖 𝑗}

Sketch. If

𝐴 = 𝐮 𝐯^{𝖳}

, both sides are

𝑢_{𝑖} 𝑢_{𝑘} 𝑣_{𝑗} 𝑣_{𝑙}

. Conversely, if

𝑎_{𝑘 𝑙} \neq 0

, the condition gives

𝑎_{𝑖 𝑗} =

𝑎_{𝑖 𝑙} (𝑎_{𝑘 𝑗} / 𝑎_{𝑘 𝑙})

, so

𝐴 = 𝐮 𝐯^{𝖳}

with

𝐮

column

𝑙

and

𝑣_{𝑗} =

𝑎_{𝑘 𝑗} / 𝑎_{𝑘 𝑙}

. (b)

4 - 𝑡^{2} = 0

and

2 𝑡^{2} - 8 = 0

, and the remaining condition holds for all

𝑡

𝑡 = \pm 2

(a) Only if. If $𝐴 = 0$ , both sides are $0$ . If $rank 𝐴 = 1$ , then $𝐴 = 𝐮 𝐯^{𝖳}$ (Proposition 4.3.16), so $𝑎_{𝑖 𝑗} = 𝑢_{𝑖} 𝑣_{𝑗}$ , and both sides equal $𝑢_{𝑖} 𝑢_{𝑘} 𝑣_{𝑗} 𝑣_{𝑙}$ .

If. Suppose the condition holds. If $𝐴 = 0$ , then $rank 𝐴 = 0$ . Otherwise fix $𝑘, 𝑙$ with $𝑎_{𝑘 𝑙} \neq 0$ . For all $𝑖, 𝑗$ , the condition gives

𝑎_{𝑖 𝑗} = 𝑎_{𝑖 𝑙} \cdot \frac{𝑎_{𝑘 𝑗}}{𝑎_{𝑘 𝑙}} .

Let $𝐮 =$ $(𝑎_{1 𝑙}, \dots, 𝑎_{𝑚 𝑙})$ , column $𝑙$ of $𝐴$ , and $𝐯 =$ $(𝑎_{𝑘 1}, \dots, 𝑎_{𝑘 𝑛}) / 𝑎_{𝑘 𝑙}$ . Then $𝑎_{𝑖 𝑗} = 𝑢_{𝑖} 𝑣_{𝑗}$ for all $𝑖, 𝑗$ , so $𝐴 = 𝐮 𝐯^{𝖳}$ , and $rank 𝐴 \leq 1$ by Proposition 4.3.16 (in fact $= 1$ , since $𝑢_{𝑘} = 𝑎_{𝑘 𝑙} \neq 0$ and $𝑣_{𝑙} = 1$ ).

(b) The matrix is nonzero, so it has rank $1$ exactly when all the conditions in (a) hold. With rows $1, 2$ and columns $(1, 2)$ , $(1, 3)$ , $(2, 3)$ they read $1 \cdot 4 = 𝑡 \cdot 𝑡$ , $1 \cdot 2 𝑡 = 2 \cdot 𝑡$ , and $𝑡 \cdot 2 𝑡 = 2 \cdot 4$ (the other choices of indices repeat these or are trivial). The second always holds, and the first and third both say $𝑡^{2} = 4$ . So $𝑡 = 2$ or $𝑡 = - 2$ , giving $(\begin{matrix} 1 & 2 & 2 \\ 2 & 4 & 4 \end{matrix})$ and $(\begin{matrix} 1 & - 2 & 2 \\ - 2 & 4 & - 4 \end{matrix})$ .

Exercise 4.3.42.hard Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . Show that

rank 𝐴 + rank (𝐼_{𝑛} - 𝐴) = 𝑛

if and only if $𝐴^{2} = 𝐴$ .

Solution.

Uses. Proposition 4.3.20 (Rank is subadditive), Exercise 4.3.30, Theorem 4.2.11 (Rank–nullity), Proposition 4.1.21 (Dimensions of subspaces)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. One inequality always holds:

𝐼_{𝑛} = 𝐴 + (𝐼_{𝑛} - 𝐴)

Hint 2. If

𝐴^{2} = 𝐴

, then

𝐴 (𝐼_{𝑛} - 𝐴) = 0

. Which inequality bounds

rank 𝐴 +

rank (𝐼_{𝑛} - 𝐴)

from above?

Hint 3. Conversely, show

ker 𝐴 \subseteq im (𝐼_{𝑛} - 𝐴)

, compare dimensions, and conclude

𝐴 (𝐼_{𝑛} - 𝐴) = 0

Sketch. Always

𝑛 =

rank 𝐼_{𝑛} \leq

rank 𝐴 +

rank (𝐼_{𝑛} - 𝐴)

. If

𝐴^{2} = 𝐴

, then

𝐴 (𝐼_{𝑛} - 𝐴) = 0

, and Sylvester gives

rank 𝐴 +

rank (𝐼_{𝑛} - 𝐴) \leq

𝑛

. Conversely,

𝐴 𝐱 = 𝟎

implies

𝐱 = (𝐼_{𝑛} - 𝐴) 𝐱

, so

ker 𝐴 \subseteq im (𝐼_{𝑛} - 𝐴)

; the hypothesis says

dim ker 𝐴 =

𝑛 -

rank 𝐴 =

rank (𝐼_{𝑛} - 𝐴)

, so

ker 𝐴 = im (𝐼_{𝑛} - 𝐴)

, that is,

𝐴 (𝐼_{𝑛} - 𝐴) = 0

By Proposition 4.3.20, $𝑛 =$ $rank 𝐼_{𝑛} =$ $rank (𝐴 + (𝐼_{𝑛} - 𝐴)) \leq$ $rank 𝐴 +$ $rank (𝐼_{𝑛} - 𝐴)$ for every $𝐴$ .

If. Suppose $𝐴^{2} = 𝐴$ . Then $𝐴 (𝐼_{𝑛} - 𝐴) =$ $𝐴 -$ $𝐴^{2} =$ $0$ , so by Exercise 4.3.30(b), $rank 𝐴 +$ $rank (𝐼_{𝑛} - 𝐴) \leq$ $𝑛$ . With the inequality above, equality holds.

Only if. Suppose $rank 𝐴 +$ $rank (𝐼_{𝑛} - 𝐴) =$ $𝑛$ . If $𝐴 𝐱 = 𝟎$ , then $𝐱 =$ $𝐱 -$ $𝐴 𝐱 =$ $(𝐼_{𝑛} - 𝐴) 𝐱$ , so $ker 𝐴 \subseteq im (𝐼_{𝑛} - 𝐴)$ . By Theorem 4.2.11 and the hypothesis, $dim ker 𝐴 =$ $𝑛 -$ $rank 𝐴 =$ $rank (𝐼_{𝑛} - 𝐴) =$ $dim im (𝐼_{𝑛} - 𝐴)$ . By Proposition 4.1.21(b), $ker 𝐴 = im (𝐼_{𝑛} - 𝐴)$ . So $𝐴 (𝐼_{𝑛} - 𝐴) 𝐱 = 𝟎$ for every $𝐱$ , that is, $𝐴 - 𝐴^{2} = 0$ .

So a matrix is idempotent exactly when the ranks of $𝐴$ and $𝐼_{𝑛} - 𝐴$ are as small as subadditivity allows. Geometrically, $𝐹^{𝑛}$ then splits into $im 𝐴$ , on which $𝐴$ acts as the identity, and $ker 𝐴 = im (𝐼_{𝑛} - 𝐴)$ ; this is the decomposition of Section 4.4.

Exercise 4.3.43.hard Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ satisfy $𝐴^{2} = 𝐴$ , and let $𝑟 = rank 𝐴 \geq 1$ .

(a)Let $𝐴 = 𝐶 𝑅$ be a factorization with $𝐶 \in 𝐹^{𝑛 \times 𝑟}$ and $𝑅 \in 𝐹^{𝑟 \times 𝑛}$ , as in Theorem 4.3.21. Show that $𝑅 𝐶 = 𝐼_{𝑟}$ .
(b)Deduce that $tr 𝐴 = 𝑟 \cdot 1$ , the sum of $𝑟$ copies of $1$ in $𝐹$ .
(c)Deduce that over $ℚ$ , $ℝ$ , or $ℂ$ , the rank of an idempotent matrix equals its trace. Show by an example that over $𝔽_{2}$ the rank of an idempotent is not determined by its trace.

Solution.

Uses. Theorem 4.3.21 (Column–row factorization), Proposition 3.5.9 (Left inverses), Proposition 3.5.8 (Right inverses from the pivots), Proposition 2.4.28 (Cyclicity of the trace), Proposition 4.3.23 (Factorizations through $𝐹^{𝑘}$ )

Techniques. Cyclicity of trace (Technique 2.4.29)

Hint 1.

𝐶

has independent columns and

𝑅

has independent rows. What one-sided inverses do they have?

Hint 2. Multiply

𝐶 𝑅 𝐶 𝑅 = 𝐶 𝑅

on the left by a left inverse of

𝐶

and on the right by a right inverse of

𝑅

Hint 3.

tr (𝐶 𝑅) = tr (𝑅 𝐶)

Sketch.

rank 𝐶 = 𝑟

= number of columns, so

𝐿 𝐶 = 𝐼_{𝑟}

for some

𝐿

;

rank 𝑅 = 𝑟

= number of rows, so

𝑅 𝑍 = 𝐼_{𝑟}

for some

𝑍

. Multiplying

𝐶 (𝑅 𝐶) 𝑅 = 𝐶 𝑅

𝐿

on the left and

𝑍

on the right gives

𝑅 𝐶 = 𝐼_{𝑟}

. Then

tr 𝐴 =

tr (𝐶 𝑅) =

tr (𝑅 𝐶) =

tr 𝐼_{𝑟} =

𝑟 \cdot

1

. Over

𝔽_{2}

𝐼_{2}

and

0

both have trace

0

(a) By Theorem 4.3.21, $rank 𝐶 = 𝑟$ , the number of columns of $𝐶$ , and $rank 𝑅 = 𝑟$ , the number of rows of $𝑅$ . By Proposition 3.5.9 and Proposition 3.5.8, there are $𝐿 \in 𝐹^{𝑟 \times 𝑛}$ with $𝐿 𝐶 = 𝐼_{𝑟}$ and $𝑍 \in 𝐹^{𝑛 \times 𝑟}$ with $𝑅 𝑍 = 𝐼_{𝑟}$ . Since $𝐴^{2} = 𝐴$ , $𝐶 (𝑅 𝐶) 𝑅 = 𝐶 𝑅$ . Multiplying on the left by $𝐿$ and on the right by $𝑍$ ,

\begin{aligned} 𝑅 𝐶 & = (𝐿 𝐶) (𝑅 𝐶) (𝑅 𝑍) = 𝐿 (𝐶 𝑅 𝐶 𝑅) 𝑍 \\ = 𝐿 (𝐶 𝑅) 𝑍 = (𝐿 𝐶) (𝑅 𝑍) = 𝐼_{𝑟} . \end{aligned}

(The same argument works for any factorization $𝐴 = 𝑋 𝑌$ with inner size $𝑟$ , by Proposition 4.3.23.)

(b) By Proposition 2.4.28, $tr 𝐴 =$ $tr (𝐶 𝑅) =$ $tr (𝑅 𝐶) =$ $tr 𝐼_{𝑟} =$ $𝑟 \cdot$ $1$ .

(c) In $ℚ$ , $ℝ$ , and $ℂ$ , $𝑟 \cdot 1$ is the integer $𝑟$ , so $tr 𝐴 = rank 𝐴$ by (b); the idempotent $𝐴 = 0$ has trace and rank $0$ . Over $𝔽_{2}$ , the idempotents $𝐼_{2}$ and $0$ have trace $1 + 1 = 0$ and $0$ , but ranks $2$ and $0$ . In general, (b) determines $rank 𝐴$ only modulo the characteristic of $𝐹$ . For example, the rank of the idempotent $𝐴 = (\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix})$ is $1 = tr 𝐴$ , which (b) predicts over any field.

Exercise 4.3.44.hard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have rank $𝑟 \geq 1$ , and suppose $𝐴 = 𝐶 𝑅 = 𝐶^{'} 𝑅^{'}$ with $𝐶, 𝐶^{'} \in 𝐹^{𝑚 \times 𝑟}$ and $𝑅, 𝑅^{'} \in 𝐹^{𝑟 \times 𝑛}$ .

(a)Show that there is exactly one invertible $𝑃 \in 𝐹^{𝑟 \times 𝑟}$ with $𝐶^{'} = 𝐶 𝑃$ , and that then $𝑅^{'} = 𝑃^{- 1} 𝑅$ .
(b)Deduce that the factorization of Theorem 4.3.21 is the only factorization $𝐴 = 𝐶^{'} 𝑅^{'}$ with inner size $𝑟$ in which $𝑅^{'}$ is in RREF.

Solution.

Uses. Proposition 4.3.23 (Factorizations through $𝐹^{𝑘}$ ), Proposition 2.4.8 (Four views of the product), Proposition 3.5.9 (Left inverses), Proposition 3.5.8 (Right inverses from the pivots), Corollary 3.5.21 (Invertibility and row equivalence), Corollary 3.3.18 (RREF and row equivalence)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. By Proposition 4.3.23(b), the columns of

𝐶

and of

𝐶^{'}

are both bases of

im 𝐴

. Express one basis in terms of the other.

Hint 2.

𝐶

has a left inverse, so

𝐶 𝑋 = 𝐶 𝑌

implies

𝑋 = 𝑌

Hint 3. For (b),

𝑅^{'} = 𝑃^{- 1} 𝑅

says that

𝑅^{'}

and

𝑅

are row equivalent.

Sketch. The columns of

𝐶

form a basis of

im 𝐴

and the columns of

𝐶^{'}

lie in it, so

𝐶^{'} = 𝐶 𝑃

for a unique

𝑃

; likewise

𝐶 = 𝐶^{'} 𝑄

, and

𝐶 𝑃 𝑄 = 𝐶

gives

𝑃 𝑄 = 𝐼_{𝑟}

by cancelling

𝐶

, so

𝑃

is invertible. Then

𝐶 𝑅 = 𝐶 𝑃 𝑅^{'}

gives

𝑅 = 𝑃 𝑅^{'}

. (b) If

𝑅^{'}

is in RREF, then

𝑅^{'} = 𝑃^{- 1} 𝑅

is row equivalent to the RREF matrix

𝑅

, so

𝑅^{'} = 𝑅

, and then

𝑃 = 𝐼_{𝑟}

and

𝐶^{'} = 𝐶

By Proposition 4.3.23(b), the columns of $𝐶$ form a basis of $im 𝐴$ , and so do the columns of $𝐶^{'}$ . Since $rank 𝐶 = 𝑟$ is the number of columns of $𝐶$ , $𝐶$ has a left inverse $𝐿$ (Proposition 3.5.9), so $𝐶 𝑋 = 𝐶 𝑌$ implies $𝑋 =$ $𝐿 𝐶 𝑋 =$ $𝐿 𝐶 𝑌 =$ $𝑌$ . That is, $𝐶$ can be cancelled on the left.

(a) Each column of $𝐶^{'}$ lies in $im 𝐴$ , so it is a combination of the columns of $𝐶$ ; collecting the coefficients into the columns of $𝑃 \in 𝐹^{𝑟 \times 𝑟}$ gives $𝐶^{'} = 𝐶 𝑃$ (Proposition 2.4.8(b)). Symmetrically, $𝐶 = 𝐶^{'} 𝑄$ for some $𝑄$ . Then $𝐶 (𝑃 𝑄) =$ $𝐶^{'} 𝑄 =$ $𝐶 =$ $𝐶 𝐼_{𝑟}$ , so $𝑃 𝑄 = 𝐼_{𝑟}$ by cancellation. Likewise $𝐶^{'} (𝑄 𝑃) = 𝐶^{'}$ and $𝐶^{'}$ can be cancelled, so $𝑄 𝑃 = 𝐼_{𝑟}$ . So $𝑃$ is invertible. It is unique: if also $𝐶^{'} = 𝐶 𝑃^{'}$ , then $𝐶 𝑃 = 𝐶 𝑃^{'}$ gives $𝑃 = 𝑃^{'}$ . Finally, $𝐶 𝑅 =$ $𝐴 =$ $𝐶^{'} 𝑅^{'} =$ $𝐶 𝑃 𝑅^{'}$ , so $𝑅 = 𝑃 𝑅^{'}$ by cancellation, and $𝑅^{'} = 𝑃^{- 1} 𝑅$ .

(b) Let $𝑅$ be the first $𝑟$ rows of $rref (𝐴)$ and suppose $𝑅^{'}$ is in RREF. By (a), $𝑅^{'} = 𝑃^{- 1} 𝑅$ with $𝑃^{- 1}$ invertible, so $𝑅^{'} \sim 𝑅$ (Corollary 3.5.21); both are in RREF, so $𝑅^{'} = 𝑅$ by Corollary 3.3.18(c). Then $𝑅 = 𝑃 𝑅$ , and since $𝑅$ has a right inverse $𝑍$ (Proposition 3.5.8), $𝐼_{𝑟} =$ $𝑅 𝑍 =$ $𝑃 𝑅 𝑍 =$ $𝑃$ . So $𝐶^{'} = 𝐶$ . (Problem 3.17 proved the uniqueness of $𝐶$ for this $𝑅$ by the same cancellation.)

Exercise 4.3.45.challenge Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ .

(a)Suppose $rank (𝐴^{2}) =$ $rank 𝐴 =$ $𝑟 \geq$ $1$ , and let $𝐴 = 𝐶 𝑅$ be a factorization with inner size $𝑟$ . Show that $𝑅 𝐶 \in 𝐹^{𝑟 \times 𝑟}$ is invertible.
(b)Under the hypothesis of (a), show that $𝑋 = 𝐶 {(𝑅 𝐶)}^{- 2} 𝑅$ satisfies
$𝐴 𝑋 𝐴 = 𝐴, 𝑋 𝐴 𝑋 = 𝑋, 𝐴 𝑋 = 𝑋 𝐴 .$
(c)Conversely, show that if some $𝑋 \in 𝐹^{𝑛 \times 𝑛}$ satisfies the three equations in (b), then $rank (𝐴^{2}) = rank 𝐴$ .

Solution.

Uses. Proposition 4.3.23 (Factorizations through $𝐹^{𝑘}$ ), Proposition 3.5.9 (Left inverses), Proposition 3.5.8 (Right inverses from the pivots), Theorem 4.3.3 (Rank of a product), Proposition 4.3.1 (Invertible factors preserve rank), Corollary 3.5.25 (The invertible matrix theorem)

Hint 1.

𝐴^{2} = 𝐶 (𝑅 𝐶) 𝑅

. Use one-sided inverses of

𝐶

and

𝑅

to show

rank (𝑅 𝐶) =

rank (𝐴^{2})

Hint 2. For (b), compute

𝐴 𝑋

and

𝑋 𝐴

first; both equal

𝐶 {(𝑅 𝐶)}^{- 1} 𝑅

Hint 3. For (c),

𝐴 = 𝐴 𝑋 𝐴 = 𝐴^{2} 𝑋

Sketch. (a) With

𝐿 𝐶 = 𝐼_{𝑟}

and

𝑅 𝑍 = 𝐼_{𝑟}

𝑅 𝐶 =

𝐿 (𝐶 𝑅 𝐶 𝑅) 𝑍 =

𝐿 𝐴^{2} 𝑍

, so

rank (𝑅 𝐶) \geq

rank (𝐴^{2}) =

𝑟

and

𝑅 𝐶

is invertible. (b)

𝐴 𝑋 =

𝐶 𝑅 𝐶 {(𝑅 𝐶)}^{- 2} 𝑅 =

𝐶 {(𝑅 𝐶)}^{- 1} 𝑅

and

𝑋 𝐴 =

𝐶 {(𝑅 𝐶)}^{- 2} 𝑅 𝐶 𝑅 =

𝐶 {(𝑅 𝐶)}^{- 1} 𝑅

; then

𝐴 𝑋 𝐴 =

𝐶 {(𝑅 𝐶)}^{- 1} 𝑅 𝐶 𝑅 =

𝐶 𝑅

and

𝑋 𝐴 𝑋 =

𝐶 {(𝑅 𝐶)}^{- 1} 𝑅 𝐶 {(𝑅 𝐶)}^{- 2} 𝑅 =

𝑋

. (c)

rank 𝐴 =

rank (𝐴^{2} 𝑋) \leq

rank (𝐴^{2}) \leq

rank 𝐴

By Proposition 4.3.23(b), $𝐶$ has $𝑟$ independent columns and $𝑅$ has $𝑟$ independent rows, so $rank 𝐶 = rank 𝑅 = 𝑟$ , and there are $𝐿$ and $𝑍$ with $𝐿 𝐶 = 𝐼_{𝑟}$ and $𝑅 𝑍 = 𝐼_{𝑟}$ (Proposition 3.5.9, Proposition 3.5.8).

(a) $𝐴^{2} = 𝐶 𝑅 𝐶 𝑅$ , so $𝐿 𝐴^{2} 𝑍 =$ $(𝐿 𝐶) (𝑅 𝐶) (𝑅 𝑍) =$ $𝑅 𝐶$ . By Theorem 4.3.3, $rank (𝑅 𝐶) =$ $rank (𝐿 𝐴^{2} 𝑍) \leq$ $rank (𝐴^{2})$ , and also $rank (𝐴^{2}) =$ $rank (𝐶 (𝑅 𝐶) 𝑅) \leq$ $rank (𝑅 𝐶)$ . So $rank (𝑅 𝐶) =$ $rank (𝐴^{2}) =$ $𝑟$ , and the $𝑟 \times 𝑟$ matrix $𝑅 𝐶$ is invertible (Corollary 3.5.25).

(b) Let $𝐾 = 𝑅 𝐶$ , invertible by (a), and $𝑋 = 𝐶 𝐾^{- 2} 𝑅$ . Then

\begin{aligned} 𝐴 𝑋 & = 𝐶 𝑅 𝐶 𝐾^{- 2} 𝑅 = 𝐶 𝐾 𝐾^{- 2} 𝑅 = 𝐶 𝐾^{- 1} 𝑅, \\ 𝑋 𝐴 & = 𝐶 𝐾^{- 2} 𝑅 𝐶 𝑅 = 𝐶 𝐾^{- 2} 𝐾 𝑅 = 𝐶 𝐾^{- 1} 𝑅, \end{aligned}

so $𝐴 𝑋 = 𝑋 𝐴$ . Next, $𝐴 𝑋 𝐴 =$ $𝐶 𝐾^{- 1} 𝑅 𝐶 𝑅 =$ $𝐶 𝐾^{- 1} 𝐾 𝑅 =$ $𝐶 𝑅 =$ $𝐴$ , and

𝑋 𝐴 𝑋 = 𝐶 𝐾^{- 1} 𝑅 𝐶 𝐾^{- 2} 𝑅 = 𝐶 𝐾^{- 1} 𝐾 𝐾^{- 2} 𝑅 = 𝐶 𝐾^{- 2} 𝑅 = 𝑋 .

(c) If $𝐴 𝑋 𝐴 = 𝐴$ and $𝐴 𝑋 = 𝑋 𝐴$ , then $𝐴 =$ $𝐴 (𝑋 𝐴) =$ $𝐴 (𝐴 𝑋) =$ $𝐴^{2} 𝑋$ . By Theorem 4.3.3, $rank 𝐴 =$ $rank (𝐴^{2} 𝑋) \leq$ $rank (𝐴^{2}) \leq$ $rank 𝐴$ . So $rank (𝐴^{2}) = rank 𝐴$ .

The matrix $𝑋$ is called the group inverse of $𝐴$ . If $𝐴$ is invertible, then $𝑟 = 𝑛$ , $𝐶$ and $𝑅$ are invertible, and $𝑋 =$ $𝐶 {(𝑅 𝐶)}^{- 2} 𝑅 =$ $𝐶 𝐶^{- 1} 𝑅^{- 1} 𝐶^{- 1} 𝑅^{- 1} 𝑅 =$ $𝐴^{- 1}$ . For the projection $𝐴 =$ $(\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) =$ $𝐞_{1} 𝐞_{1}^{𝖳}$ , $𝑅 𝐶 = (1)$ and $𝑋 = 𝐴$ . For $𝑁 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ , $rank (𝑁^{2}) = 0 < 1$ , and no such $𝑋$ exists.

More practice

The practice bank has 31 exercises on this section’s topics.