Problems for Chapter 3

(a) Statement (Proposition 3.1.19). Let $𝑇:𝑉\to 𝑊$ be linear, $𝐲\in 𝑊$, and $𝑆=$$\{𝐱\in 𝑉|𝑇(𝐱)=𝐲\}$. If ${𝐱}_0\in 𝑆$, then $𝑆={𝐱}_0+ker𝑇$, and $𝐳\mapsto {𝐱}_0+𝐳$ is a bijection from $ker𝑇$ onto $𝑆$.

Proof. We prove both containments. If $𝐳\in ker𝑇$, then $𝑇({𝐱}_0+𝐳)=$$𝑇({𝐱}_0)+$$𝑇(𝐳)=$$𝐲+$$\mathrm{𝟎}=$$𝐲$, so ${𝐱}_0+𝐳\in 𝑆$. Conversely, if $𝐱\in 𝑆$, put $𝐳=𝐱-{𝐱}_0$; then $𝑇(𝐳)=$$𝑇(𝐱)-$$𝑇({𝐱}_0)=$$𝐲-$$𝐲=$$\mathrm{𝟎}$, so $𝐳\in ker𝑇$ and $𝐱=$${𝐱}_0+$$𝐳\in$${𝐱}_0+$$ker𝑇$. Hence $𝑆={𝐱}_0+ker𝑇$, so the map $𝐳\mapsto {𝐱}_0+𝐳$ sends $ker𝑇$ onto $𝑆$. It is injective, since ${𝐱}_0+𝐳={𝐱}_0+{𝐳}^{\prime }$ gives $𝐳={𝐳}^{\prime }$ after adding $-{𝐱}_0$. So it is a bijection.

(b) Let $𝑈$ be the set of $𝐲$ for which $𝐴𝐱=𝐲$ has exactly one solution. Every $𝐲\in 𝑈$ makes the system consistent, so $𝑈\subseteq im{𝑇}_{𝐴}$ (Proposition 3.1.8(a)).

Case $ker{𝑇}_{𝐴}=\{\mathrm{𝟎}\}$. Let $𝐲\in im{𝑇}_{𝐴}$. The system $𝐴𝐱=𝐲$ is consistent, so by Corollary 3.1.22(a) it has exactly one solution, and $𝐲\in 𝑈$. Hence $𝑈=im{𝑇}_{𝐴}$.

Case $ker{𝑇}_{𝐴}\ne \{\mathrm{𝟎}\}$. Then $ker{𝑇}_{𝐴}$ contains $\mathrm{𝟎}$ (Proposition 2.1.4) and some $𝐳\ne \mathrm{𝟎}$, so it has at least two elements. If $𝐴𝐱=𝐲$ is consistent, its solution set is in bijection with $ker{𝑇}_{𝐴}$ by (a), applied to $𝑇={𝑇}_{𝐴}$, so it has at least two elements. If it is inconsistent, it has none. Either way $𝐲\notin 𝑈$, so $𝑈=\varnothing$.

So the set is $im{𝑇}_{𝐴}$ when $ker{𝑇}_{𝐴}=\{\mathrm{𝟎}\}$, and empty otherwise. Uniqueness is all or nothing: it holds for every consistent right-hand side or for none.

(a) Statement (Theorem 3.3.17). If $𝑅,{𝑅}^{\prime }\in {𝐹}^{𝑚\times 𝑛}$ are in RREF and ${𝑅}^{\prime }=𝐺𝑅$ for an invertible $𝐺\in {𝐹}^{𝑚\times 𝑚}$, then $𝑅={𝑅}^{\prime }$.

Proof. Write ${𝐫}_{𝑗}$ and ${𝐫}_{𝑗}^{\prime }=𝐺{𝐫}_{𝑗}$ for the columns. By Corollary 3.2.17, for all scalars ${𝑥}_1,\dots ,{𝑥}_{𝑛}$,

An equation ${𝐫}_{𝑗}=$${𝑐}_1{𝐫}_1+$$\cdots +$${𝑐}_{𝑗-1}{𝐫}_{𝑗-1}$ is such a relation (with ${𝑥}_{𝑗}=-1$, ${𝑥}_{𝑙}={𝑐}_{𝑙}$ for $𝑙<𝑗$, and ${𝑥}_{𝑙}=0$ for $𝑙>𝑗$), so it holds in $𝑅$ if and only if the same equation holds in ${𝑅}^{\prime }$. Hence ${𝐫}_{𝑗}$ is a combination of the earlier columns of $𝑅$ exactly when ${𝐫}_{𝑗}^{\prime }$ is a combination of the earlier columns of ${𝑅}^{\prime }$, and by Lemma 3.3.16(c) the two matrices have the same pivot columns ${𝑝}_1<\cdots <{𝑝}_{𝑟}$. By Lemma 3.3.16(b), ${𝐫}_{{𝑝}_{𝑠}}=$${𝐞}_{𝑠}=$${𝐫}_{{𝑝}_{𝑠}}^{\prime }$. If $𝑗$ is a free column with pivot columns ${𝑝}_1,\dots ,{𝑝}_{𝑡}$ to its left, Lemma 3.3.16(d) gives the relation ${𝐫}_{𝑗}=$${\sum }_{𝑠\le 𝑡}{𝑟}_{𝑠𝑗}{𝐫}_{{𝑝}_{𝑠}}$, which therefore also holds in ${𝑅}^{\prime }$:

So every column of ${𝑅}^{\prime }$ equals the corresponding column of $𝑅$.

(b) $𝑅=\left(\begin{array}{cc}0& 1\end{array}\right)$ and ${𝑅}^{\prime }=\left(\begin{array}{cc}1& 0\end{array}\right)$ both satisfy (R1)–(R4), so they are in RREF (Theorem 3.3.12), and ${𝑅}^{\prime }=𝑅{𝐸}_{12}$ with ${𝐸}_{12}$ the $2\times 2$ swap, which is invertible. The proof of (a) breaks because right multiplication does not preserve the relations among the columns: here ${𝐫}_1=\mathrm{𝟎}$ but ${𝐫}_1^{\prime }\ne \mathrm{𝟎}$.

(c) Let $𝑅$ have pivot columns ${𝑝}_1<\cdots <{𝑝}_{𝑟}$. By Theorem 3.3.12 and Proposition 3.3.8, rows $1,\dots ,𝑟$ of $𝑅$ are nonzero and the others are zero; write ${𝐮}_1,\dots ,{𝐮}_{𝑟}\in {𝐹}^{1\times 𝑛}$ for the nonzero rows. They are linearly independent: if ${𝑐}_1{𝐮}_1+$$\cdots +$${𝑐}_{𝑟}{𝐮}_{𝑟}=$$\mathrm{𝟎}$, look at entry ${𝑝}_{𝑡}$. Column ${𝑝}_{𝑡}$ of $𝑅$ is ${𝐞}_{𝑡}$ (Lemma 3.3.16(b)), so ${𝐮}_{𝑠}$ has entry $1$ there if $𝑠=𝑡$ and $0$ otherwise, and the entry ${𝑝}_{𝑡}$ of the combination is ${𝑐}_{𝑡}$. So every ${𝑐}_{𝑡}=0$.

By Definition 2.4.1, row $𝑠$ of $𝑅𝐻$ is ${𝐮}_{𝑠}𝐻$ for $𝑠\le 𝑟$, and $\mathrm{𝟎}𝐻=\mathrm{𝟎}$ for $𝑠>𝑟$. The rows ${𝐮}_1𝐻,\dots ,{𝐮}_{𝑟}𝐻$ are again independent: if ${\sum }_{𝑠}{𝑐}_{𝑠}{𝐮}_{𝑠}𝐻=\mathrm{𝟎}$, then $\left({\sum }_{𝑠}{𝑐}_{𝑠}{𝐮}_{𝑠}\right)𝐻=$$\mathrm{𝟎}$, multiplying on the right by ${𝐻}^{-1}$ gives ${\sum }_{𝑠}{𝑐}_{𝑠}{𝐮}_{𝑠}=\mathrm{𝟎}$, and so every ${𝑐}_{𝑠}=0$. In particular each ${𝐮}_{𝑠}𝐻$ is nonzero (a list containing $\mathrm{𝟎}$ is dependent). So $𝑅𝐻$ has exactly $𝑟$ nonzero rows. Since $𝑅𝐻$ is in RREF, its pivots are the leading entries of its nonzero rows (Theorem 3.3.12), so it has $𝑟$ pivots, as $𝑅$ does.

Part (c) is the transpose of a row statement in disguise (Technique 3.2.27): the rows of $𝑅𝐻$ are the columns of ${𝐻}^{\text{𝖳}}{𝑅}^{\text{𝖳}}$, and left multiplication by an invertible matrix preserves independence of columns (Corollary 3.2.17).

(a) Statement (Theorem 3.3.23). Let $𝐴\in {𝐹}^{𝑛\times 𝑛}$, and let $𝐺$ be a product of elementary matrices with $𝐺𝐴=rref(𝐴)$. Then $𝐴$ is invertible if and only if $rref(𝐴)={𝐼}_{𝑛}$, and in that case ${𝐴}^{-1}=𝐺$.

Proof. If $rref(𝐴)={𝐼}_{𝑛}$, then $𝐺𝐴={𝐼}_{𝑛}$, and $𝐺$ is invertible (Corollary 3.2.11), so $𝐴={𝐺}^{-1}$ and $𝐴𝐺={𝐺}^{-1}𝐺={𝐼}_{𝑛}$; thus ${𝐴}^{-1}=𝐺$. Conversely, suppose $𝑅=rref(𝐴)\ne {𝐼}_{𝑛}$. If $𝑅$ had $𝑛$ pivots, they would lie in columns ${𝑝}_1<\cdots <{𝑝}_{𝑛}$ among $1,\dots ,𝑛$, forcing ${𝑝}_{𝑠}=𝑠$, and then $𝑅={𝐼}_{𝑛}$ by Proposition 3.3.8(c). So $𝑅$ has fewer than $𝑛$ pivots, and its last row is zero (Proposition 3.3.8(a)). Then the last row of $𝑅𝑋$ is zero for every $𝑋$, so $𝑅𝑋\ne {𝐼}_{𝑛}$ and $𝑅$ is not invertible. If $𝐴$ were invertible, $𝑅=𝐺𝐴$ would be invertible with inverse ${𝐴}^{-1}{𝐺}^{-1}$. So $𝐴$ is not invertible.

The algorithm. By Proposition 3.3.11, Gauss–Jordan elimination on $(𝐴|{𝐼}_{𝑛})$, scanning only the left block, ends at $(rref(𝐴)|𝐺)$, where $𝐺$ is the product of the elementary matrices of the run on $𝐴$. By the theorem, if the left block is ${𝐼}_{𝑛}$ then ${𝐴}^{-1}=𝐺$, and otherwise $𝐴$ is not invertible.

(b) Each row operation is left multiplication by an elementary matrix (Proposition 3.2.7), so at every stage the current matrix is ${𝐺}^{\prime }(𝐴|{𝐼}_{𝑛})=$$({𝐺}^{\prime }𝐴|{𝐺}^{\prime })$ for some product ${𝐺}^{\prime }$ of elementary matrices, which is invertible (Corollary 3.2.11). Let $𝐳$ be row $𝑖$ of ${𝐺}^{\prime }$, the row $𝑖$ of the right block. By Definition 2.4.1, row $𝑖$ of ${𝐺}^{\prime }𝐴$ is $𝐳𝐴$, and this is the zero row by assumption. And $𝐳\ne \mathrm{𝟎}$: otherwise row $𝑖$ of ${𝐺}^{\prime }𝑋$ would be zero for every $𝑋$, and ${𝐺}^{\prime }$ would have no right inverse.

If $𝐴$ were invertible, then $𝐳=$$𝐳(𝐴{𝐴}^{-1})=$$(𝐳𝐴){𝐴}^{-1}=$$\mathrm{𝟎}{𝐴}^{-1}=$$\mathrm{𝟎}$, a contradiction. So $𝐴$ is not invertible. The vector $𝐳$ is a certificate: anyone can check $𝐳𝐴=\mathrm{𝟎}$ by one multiplication, without redoing the elimination.

(c) Over ${𝔽}_5$ the entry $9$ is $4$. Pass $1$ adds $-2$ times row $1$ to row $2$ and $-3$ times row $1$ to row $3$:

using $-4=1$, $-5=0$, $-2=3$, and $-3=2$ in ${𝔽}_5$. Pass $2$ has its pivot at $(2,2)$; adding $-1$ times row $2$ to row $3$ makes row $3$ of the left block zero, with right block row $(2-3,0-1,1)=$$(-1,-1,1)=$$(4,4,1)$. So $𝐳=(4,4,1)$, and indeed

So $𝐴$ is not invertible over ${𝔽}_5$: there, its third row is the sum of the first two.

Over $\mathbb{Q}$ the same computation gives $𝐳𝐴=(0,0,5)\ne \mathrm{𝟎}$, so the certificate is lost. Indeed, over $\mathbb{Q}$ pass $1$ leaves the rows $(0,-4,-5)$ and $(0,-4,0)$ below the first, pass $2$ scales the first of them to $(0,1,5/4)$ and adds $4$ times it to the last, which becomes $(0,0,5)$. So a third pivot appears, $rref(𝐴)={𝐼}_3$, and $𝐴$ is invertible over $\mathbb{Q}$. Whether a matrix with integer entries is invertible can depend on the field in which the entries are read (compare Example 3.5.3).

(a) Statement (Theorem 3.5.27). Let $𝐴\in {𝐹}^{𝑚\times 𝑛}$ have rank $𝑘$, and let ${𝑁}_{𝑘}\in {𝐹}^{𝑚\times 𝑛}$ have $1$ in positions $(1,1),\dots ,(𝑘,𝑘)$ and $0$ elsewhere. Then $𝐺𝐴𝐻={𝑁}_{𝑘}$ for some invertible $𝐺\in {𝐹}^{𝑚\times 𝑚}$ and $𝐻\in {𝐹}^{𝑛\times 𝑛}$.

Proof. Let $𝐺$ be invertible with $𝐺𝐴={𝐴}_{𝑟}$ (Theorem 3.3.10), with pivot columns ${𝑝}_1<\cdots <{𝑝}_{𝑘}$ and free columns ${𝑓}_1<\cdots <{𝑓}_{\ell }$, $\ell =𝑛-𝑘$. Let $𝑃$ have columns ${𝐞}_{{𝑝}_1},$$\dots ,$${𝐞}_{{𝑝}_{𝑘}},$${𝐞}_{{𝑓}_1},$$\dots ,$${𝐞}_{{𝑓}_{\ell }}$; these are the standard basis vectors in another order, so they form a basis of ${𝐹}^{𝑛}$, and $𝑃$ is invertible (Theorem 3.5.14, Remark 3.5.7). Column $𝑗$ of ${𝐴}_{𝑟}𝑃$ is column ${𝑝}_{𝑗}$ of ${𝐴}_{𝑟}$, which is ${𝐞}_{𝑗}$, for $𝑗\le 𝑘$ (Lemma 3.3.16(b)), and column ${𝑓}_{𝑖}$ of ${𝐴}_{𝑟}$ for $𝑗=𝑘+𝑖$. All rows of ${𝐴}_{𝑟}$ below row $𝑘$ are zero, so in block form ${𝐴}_{𝑟}𝑃=\left(\begin{array}{cc}{𝐼}_{𝑘}& 𝑋\\ 0& 0\end{array}\right)$ for some $𝑋\in {𝐹}^{𝑘\times \ell }$. Let $𝑈=\left(\begin{array}{cc}{𝐼}_{𝑘}& -𝑋\\ 0& {𝐼}_{\ell }\end{array}\right)$. By block multiplication (Theorem 2.4.34), $𝑈\left(\begin{array}{cc}{𝐼}_{𝑘}& 𝑋\\ 0& {𝐼}_{\ell }\end{array}\right)=$${𝐼}_{𝑛}=$$\left(\begin{array}{cc}{𝐼}_{𝑘}& 𝑋\\ 0& {𝐼}_{\ell }\end{array}\right)𝑈$, so $𝑈$ is invertible, and

With $𝐻=𝑃𝑈$, we get $𝐺𝐴𝐻=$${𝐴}_{𝑟}𝑃𝑈=$${𝑁}_{𝑘}$. (If $𝑘=0$ or $\ell =0$, the absent blocks are simply omitted.)

(b) By (a), $𝐴={𝐺}^{-1}{𝑁}_{𝑘}{𝐻}^{-1}$. By Lemma 2.4.24, ${𝑁}_{𝑘}=$${\sum }_{𝑖=1}^{𝑘}{𝐞}_{𝑖}{𝐞}_{𝑖}^{\text{𝖳}}$, where ${𝐞}_{𝑖}\in {𝐹}^{𝑚}$ on the left and ${𝐞}_{𝑖}\in {𝐹}^{𝑛}$ on the right. So

The matrix ${𝐞}_{𝑖}{𝐞}_{𝑖}^{\text{𝖳}}$ has a single nonzero entry, a $1$ in position $(𝑖,𝑖)$. Swapping row $𝑖$ to the top gives a matrix whose only nonzero row is ${𝐞}_{𝑖}^{\text{𝖳}}$, which satisfies (R1)–(R4) and so is in RREF with one pivot (Theorem 3.3.12); so it has rank $1$. Multiplying by invertible matrices on the left (Proposition 3.5.2(c)) and on the right (Exercise 3.5.41(c)) does not change the rank, so $rank{𝐵}_{𝑖}=1$.

(c) By block multiplication,

where the left factor is $𝑚\times 𝑘$ and the right one is $𝑘\times 𝑛$. So

where $𝐶$ consists of the first $𝑘$ columns of ${𝐺}^{-1}$ and $𝑆$ of the first $𝑘$ rows of ${𝐻}^{-1}$.

Problem 3.17 finds a factorization of this shape in which $𝑆$ is the nonzero part of $rref(𝐴)$, and shows that it is unique. Section 4.3 studies such factorizations in general.

(a) We reduce $(𝐴|{𝐼}_3)$. Pass $1$ adds $-2$ times row $1$ to row $2$ and $-1$ times row $1$ to row $3$. In pass $2$, column $2$ vanishes in rows $2$ and $3$, so the pivot is at $(2,3)$, and we add $-1$ times row $2$ to row $3$. These steps are the same over any field:

Over $\mathbb{Q}$. Pass $3$ scales row $3$ by $1/5$ and clears column $5$, adding $-3$ times row $3$ to row $1$ and $5$ times row $3$ to row $2$:

So $rank𝐴=3$, with pivot columns $1,3,5$.

Over ${𝔽}_5$. Here $5=0$ and $-5=0$, so after pass $2$ the third row of the left block is zero and the algorithm halts:

So $rank𝐴=2$, with pivot columns $1,3$. The last row of $𝐺$ is a relation among the rows ${𝐫}_1,{𝐫}_2,{𝐫}_3$ of $𝐴$ (Exercise 3.3.57):

This is $\mathrm{𝟎}$ in ${𝔽}_5$ but not in $\mathbb{Q}$, and it is exactly why the third pivot disappears.

(b) Over ${𝔽}_5$ the free columns are $2,4,5$. By Corollary 3.3.19(b), with the entries of $rref(𝐴)$ as coefficients,

(Check: ${𝐚}_1+$$2{𝐚}_3=$$(1,2,1)+$$(0,2,2)=$$(1,4,3)=$${𝐚}_4$, and $3{𝐚}_1=$$(3,6,3)=$$(3,1,3)=$${𝐚}_5$.) The basic solutions (Definition 3.4.8) are

and $ker{𝑇}_{𝐴}=$$span({𝐬}_1,{𝐬}_2,{𝐬}_3)$ by Theorem 3.4.9(b).

(c) By Corollary 3.4.4, $𝐴𝐱=𝐲$ is consistent if and only if the third entry of $𝐺𝐲$ vanishes, that is, ${𝑦}_1-{𝑦}_2+{𝑦}_3=0$. The vectors satisfying it are determined by ${𝑦}_1,{𝑦}_2\in {𝔽}_5$ (then ${𝑦}_3={𝑦}_2-{𝑦}_1$), so there are $25$ of them. For $𝐲=(1,1,0)$, $𝐺𝐲=$$(1,-2+1,1-1+0)=$$(1,4,0)$, so the system is consistent, with particular solution ${𝐱}_0=(1,0,4,0,0)$ (pivot variables ${𝑥}_1=1$, ${𝑥}_3=4$, free variables $0$). Check: $𝐴{𝐱}_0=$${𝐚}_1+$$4{𝐚}_3=$$(1,2+4,1+4)=$$(1,1,0)$. By Theorem 3.4.9 the solutions are

and there are $5^3=125$ of them (Corollary 3.4.14(b)).

(d) Over $\mathbb{Q}$, $rank𝐴=3$ is the number of rows, so by Proposition 3.5.8 the matrix $𝑋=𝐵𝐺$, which has row $𝑖$ of $𝐺$ in row ${𝑝}_{𝑖}$ and zeros in the free rows, is a right inverse:

Check: the first row of $𝐴$ times the columns of $𝑋$ gives $(2/5+3/5,3/5-3/5,-3/5+3/5)=$$(1,0,0)$, and the other rows work the same way. Over ${𝔽}_5$, $rank𝐴=2<3$, so ${𝑇}_{𝐴}$ is not surjective and $𝐴$ has no right inverse (Theorem 3.5.13).

The equation $𝐴𝐱=𝜆𝐱$ says $(𝐴-𝜆{𝐼}_2)𝐱=\mathrm{𝟎}$. We row reduce $𝐴-$$𝜆{𝐼}_2=$$\left(\begin{array}{cc}-𝜆& -1\\ 1& -𝜆\end{array}\right)$ over any field. Swapping the rows and then adding $𝜆$ times row $1$ to row $2$ gives

If $1+{𝜆}^2\ne 0$, the second row has a pivot, and clearing gives ${𝐼}_2$; so $𝐴-𝜆{𝐼}_2$ is invertible (Theorem 3.3.23) and only $𝐱=\mathrm{𝟎}$ satisfies $𝐴𝐱=𝜆𝐱$. If $1+{𝜆}^2=0$, the reduced form is $\left(\begin{array}{cc}1& -𝜆\\ 0& 0\end{array}\right)$, so $𝐴-𝜆{𝐼}_2$ is not invertible, and by Theorem 3.4.9 the solutions are the multiples of the basic solution $(𝜆,1)$. (Check: $𝐴(𝜆,1)=$$(-1,𝜆)=$$({𝜆}^2,𝜆)=$$𝜆(𝜆,1)$, using ${𝜆}^2=-1$.)

So we need the solutions of ${𝜆}^2=-1$ in each field.

• $ℝ$: none, since ${𝜆}^2\ge 0>-1$. So $𝐴-𝜆{𝐼}_2$ is invertible for every real $𝜆$.
• $ℂ$: $𝜆=\pm 𝑖$, with $𝐱\in span((𝑖,1))$, respectively $span((-𝑖,1))$.
• ${𝔽}_2$: $-1=1$, and $𝜆=1$ works ($0^2=0$ does not). The solutions are the multiples of $(1,1)$, that is, $(0,0)$ and $(1,1)$.
• ${𝔽}_3$: the squares are $0,1,1$, and $-1=2$ is not among them. No $𝜆$.
• ${𝔽}_5$: $-1=4=2^2=3^2$, so $𝜆=2$ or $3$, with $𝐱\in span((2,1))$, respectively $span((3,1))$.

Over $ℝ$, ${𝑇}_{𝐴}$ rotates the plane by $90°$, so no nonzero vector is sent to a multiple of itself, and the computation agrees. Whether such vectors exist depends on the field, through the single equation ${𝜆}^2=-1$; Section 7.2 takes this up.

(a) The step “every row receives a pivot” is wrong. A pass of Gauss–Jordan elimination creates a pivot only in a column that has a nonzero entry in an unpivoted row, and the algorithm halts as soon as the unpivoted rows are zero (step 1 of Algorithm 3.3.1). The count of rows and columns gives $rank𝐴\le min(𝑚,𝑛)$ (Proposition 3.5.2(a)), an upper bound, not equality. For example, $𝐴=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$ has $𝑚=𝑛=2$ and $rref(𝐴)=\left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right)$, so $rank𝐴=1<2$. It has no right inverse: if $𝐴𝑋={𝐼}_2$, then the two rows of $𝐴𝑋$ would be equal (both rows of $𝐴$ are equal), but the rows of ${𝐼}_2$ are not. The smallest counterexample is $𝐴=(0)\in {𝐹}^{1\times 1}$.

(b) The first step is wrong: Theorem 3.5.19 applies only to invertible matrices, and only those are products of elementary matrices (Corollary 3.2.11). For $𝐴=0$ and $𝐵={𝐼}_{𝑚}$, $rank(𝐴𝐵)=$$rank0=$$0$, while $rank𝐵=𝑚\ge 1$. The argument does prove the claim when $𝐴$ is invertible, which is Proposition 3.5.2(c). (In general only $rank(𝐴𝐵)\le rank𝐵$ holds; see Section 4.3.)

(a) True. If $𝐴𝐱=𝐲$ has exactly one solution, then $ker{𝑇}_{𝐴}=\{\mathrm{𝟎}\}$ by Corollary 3.1.22(a). By Theorem 3.5.12, $rank𝐴=𝑛$, and $𝑛=rank𝐴\le 𝑚$.

(b) True. Let $𝐱\in {𝐹}^{𝑛}$ and $𝐲=𝐴𝐱$. Then $𝐱$ solves $𝐴𝐱=𝐲$, so by hypothesis it solves $𝐵𝐱=𝐲$, that is, $𝐵𝐱=𝐴𝐱$. With $𝐱={𝐞}_{𝑗}$, column $𝑗$ of $𝐵$ equals column $𝑗$ of $𝐴$, for every $𝑗$.

(c) True. By Exercise 3.4.37, ${𝑥}_{𝑗}$ is a free variable of $𝐴$ if and only if some $𝐱\in ker{𝑇}_{𝐴}$ has ${𝑥}_{𝑗}=1$ and ${𝑥}_{𝑙}=0$ for all $𝑙>𝑗$. This condition involves only $ker{𝑇}_{𝐴}$, so $𝐴$ and $𝐵$ have the same free columns, and by Proposition 3.5.2(b), $rank𝐴=$$𝑛-$$(\text{number of free columns})=$$rank𝐵$. The number of rows plays no role.

(d) False. Let $𝐴=\left(\begin{array}{cc}0& 1\end{array}\right)$ and $𝐻={𝐸}_{12}$. Both $𝐴$ and $𝐴𝐻=\left(\begin{array}{cc}1& 0\end{array}\right)$ are in RREF (Theorem 3.3.12), with pivot columns $2$ and $1$ respectively.

(e) True. Write $rref(𝐴)=𝐺𝐴$ with $𝐺$ invertible (Theorem 3.3.10). Column $𝑗$ of $𝐺𝐴$ is $𝐺{𝐚}_{𝑗}$, so if it is zero, then ${𝐚}_{𝑗}=$${𝐺}^{-1}𝐺{𝐚}_{𝑗}=$$\mathrm{𝟎}$.

(f) False. The matrix units ${𝐞}_1{𝐞}_1^{\text{𝖳}}=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)$ and ${𝐞}_2{𝐞}_2^{\text{𝖳}}=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$ each have exactly one nonzero column, so by Proposition 3.5.2(d) each has rank $1$. Their sum ${𝐼}_2$ has rank $2$. So the set is not closed under addition.

Write $𝑝=$${𝑎}_0+$${𝑎}_1𝑥+$$\cdots +$${𝑎}_{𝑛}{𝑥}^{𝑛}$, so that $𝑝$ corresponds to $𝐚=$$({𝑎}_0,\dots ,{𝑎}_{𝑛})\in$${𝐹}^{𝑛+1}$. By Definition 1.2.17, $𝑝({𝑐}_{𝑖})={𝑑}_{𝑖}$ reads ${𝑎}_0+$${𝑎}_1{𝑐}_{𝑖}+$$\cdots +$${𝑎}_{𝑛}{𝑐}_{𝑖}^{𝑛}=$${𝑑}_{𝑖}$. So the conditions form the linear system $𝑊𝐚=𝐝$, where $𝐝=({𝑑}_1,\dots ,{𝑑}_{𝑘})$ and $𝑊\in {𝐹}^{𝑘\times (𝑛+1)}$ has rows $(1,{𝑐}_{𝑖},{𝑐}_{𝑖}^2,\dots ,{𝑐}_{𝑖}^{𝑛})$, the matrix of Exercise 3.4.39 with $𝑚=𝑘$ and $𝑑=𝑛$.

(a) Since $𝑘\le 𝑛+1$, Exercise 3.4.39(b) shows that ${𝑊}_{𝑟}$ has a pivot in every row, so $rank𝑊=𝑘$ and the system is consistent for every $𝐝$ (Proposition 3.4.16). It has $(𝑛+1)-𝑘$ free columns (Proposition 3.5.2(b)), so by Corollary 3.4.14(b) it has exactly ${𝑞}^{𝑛+1-𝑘}$ solutions. Each solution $𝐚$ is one polynomial.

(b) Since $𝑘>𝑛+1$, Exercise 3.4.39(a) shows that ${𝑊}_{𝑟}$ has a pivot in every column, so $𝑊𝐚=\mathrm{𝟎}$ has only the trivial solution (Proposition 3.4.15), and every system $𝑊𝐚=𝐝$ has at most one solution (Corollary 3.1.22). By Exercise 3.4.39(b), ${𝑊}_{𝑟}$ does not have a pivot in every row, so some $𝑊𝐚=𝐝$ is inconsistent (Proposition 3.4.16).

(c) Here $𝑞=7$, $𝑛=4$, and the nodes $1,2,4$ are distinct, so $𝑘=3\le 5$ and there are $7^{5-3}=49$ such polynomials. Adding the condition $𝑝(0)=0$ gives $𝑘=4$ distinct nodes $0,1,2,4$, and $7^{5-4}=7$ polynomials.

In words: each condition at a new node cuts the number of polynomials by a factor of $𝑞$, until there are $𝑛+1$ conditions and exactly one polynomial is left (Theorem 3.4.24).

(a) The columns of $𝑀=(𝐴|{𝐼}_{𝑚})$ are ${𝐚}_1,$$\dots ,$${𝐚}_{𝑛},$${𝐞}_1,$$\dots ,$${𝐞}_{𝑚}$. By Corollary 3.3.19(a), applied to $𝑀$, column $𝑗$ is a pivot column if and only if it is not a linear combination of columns $1,\dots ,𝑗-1$. For $𝑗\le 𝑛$ these are ${𝐚}_1,\dots ,{𝐚}_{𝑗-1}$, and ${𝐚}_{𝑗}$ is not a combination of them because the list ${𝐚}_1,\dots ,{𝐚}_{𝑛}$ is independent (a combination would give a nontrivial relation with coefficient $-1$ on ${𝐚}_{𝑗}$). So columns $1,\dots ,𝑛$ are pivot columns; let the others be $𝑛+$${𝑖}_1<$$\cdots <$$𝑛+$${𝑖}_{𝑡}$. Let $\mathrm{𝒫︀}=$${𝐚}_1,$$\dots ,$${𝐚}_{𝑛},$${𝐞}_{{𝑖}_1},$$\dots ,$${𝐞}_{{𝑖}_{𝑡}}$ be the list of pivot columns, in order.