Chapter 14

Let \(A \in R^{m \times n} .\) Show that if \(v A=0_{R}^{1 \times n}\) for all \(v \in R^{1 \times m},\) then \(A=0_{R}^{m \times n} .\)

Let \(\sigma: M \rightarrow N\) and \(\tau: N \rightarrow P\) be \(R\) -linear maps, and suppose that \(M, N,\) and \(P\) have bases \(S, \mathcal{T},\) and \(\mathcal{U},\) respectively. Show that $$\operatorname{Mat}_{\mathcal{S}, \mathcal{V}}(\tau \circ \sigma)=\operatorname{Mat}_{\mathcal{S}, \mathcal{T}}(\sigma) \cdot \operatorname{Mat}_{\mathcal{T}, \mathcal{V}}(\tau)$$.

Let \(V\) be a vector space over a field \(F\) with basis \(\mathcal{S}=\left\\{\alpha_{i}\right\\}_{i=1}^{m} .\) Suppose that \(U\) is a subspace of \(V\) of dimension \(\ell

Design and analyze a probabilistic algorithm that takes as input matrices \(A, B, C \in \mathbb{Z}_{p}^{m \times m},\) where \(p\) is a prime. The algorithm should run in time \(O\left(m^{2} \operatorname{len}(p)^{2}\right)\) and should output either "yes" or "no" so that the following holds: \- if \(C=A B,\) then the algorithm should always output "yes"; \- if \(C \neq A B,\) then the algorithm should output "no" with probability at least 0.999.

Let \(R\) be a ring, and let \(A\) be a square matrix over \(R\). Let us call \(B\) a left inverse of \(A\) if \(B A=I,\) and let us call \(C\) a right inverse of \(A\) if \(A C=I\) (a) Show that if \(A\) has both a left inverse \(B\) and a right inverse \(C,\) then \(B=C\) and hence \(A\) is invertible. (b) Assume that \(R\) is a field. Show that if \(A\) has either a left inverse or a right inverse, then \(A\) is invertible.

Show that if \(A\) and \(B\) are two square matrices over a field such that their product \(A B\) is invertible, then both \(A\) and \(B\) themselves must be invertible.

Show that if \(A\) is a square matrix over an arbitrary ring, and \(A^{k}\) is invertible for some \(k>0,\) then \(A\) is invertible.

For each type of elementary row operation, describe the matrix \(X\) which corresponds to it, as well as \(X^{-1}\).

Given a matrix \(B \in F^{m \times n}\) in reduced row echelon form, show how to compute its pivot sequence using \(O(n)\) operations in \(F\).

Show that the matrix \(B\) is uniquely determined by \(A\); more precisely, show that if \(X^{\prime} A=B^{\prime}\), where \(X^{\prime}\) is an invertible \(m \times m\) matrix, and \(B^{\prime}\) is in reduced row echelon form, then \(B^{\prime}=B\).

Let \(p\) be a prime. A matrix \(A \in \mathbb{Z}^{m \times m}\) is called invertible modulo \(p\) if there exists a matrix \(B \in \mathbb{Z}^{m \times m}\) such that \(A B \equiv B A \equiv I(\bmod p),\) where \(I\) is the \(m \times m\) integer identity matrix. Here, two matrices are considered congruent with respect to a given modulus if their corresponding entries are congruent. Show that \(A\) is invertible modulo \(p\) if and only if \(A\) is invertible over \(\mathbb{Q},\) and the entries of \(A^{-1}\) lie in \(\mathbb{Q}^{(p)}\) (see Example 7.26).

Let \(R\) be the ring \(\mathbb{Z}_{\ell},\) where \(\ell>1\) is an integer. You are given a matrix \(A \in R^{m \times n} .\) Show how to efficiently compute \(X \in R^{m \times m}\) and \(B \in R^{m \times n}\) such that \(X A=B, X\) is invertible, and \(B\) is in row echelon form. Your algorithm should run in time \(O\left(m n(m+n) \operatorname{len}(\ell)^{2}\right) .\) Hint: to zero-out entries, you should use "rotations" \(-\) for integers \(a, b, d, s, t\) with $$d=\operatorname{gcd}(a, b) \neq 0 \text { and } a s+b t=d$$ and for row indices \(r, i,\) a rotation simultaneously updates rows \(r\) and \(i\) of a matrix \(C\) as follows: $$\left(\operatorname{Row}_{r}(C), \operatorname{Row}_{i}(C)\right) \leftarrow\left(s \operatorname{Row}_{r}(C)+t \operatorname{Row}_{i}(C),-\frac{b}{d} \operatorname{Row}_{r}(C)+\frac{a}{d} \operatorname{Row}_{i}(C)\right)$$ observe that if \(C(r, j)=[a]_{\ell}\) and \(C(i, j)=[b]_{\ell}\) before applying the rotation, then \(C(r, j)=[d]_{\ell}\) and \(C(i, j)=[0]_{\ell}\) after the rotation.

Let \(\left\\{v_{i}\right\\}_{i=1}^{n}\) be a family of vectors, where \(v_{i} \in \mathbb{R}^{1 \times \ell}\) for each \(i=1, \ldots, n .\) We say that \(\left\\{v_{i}\right\\}_{i=1}^{n}\) is pairwise orthogonal if \(v_{i} v_{j}^{\top}=0\) for all \(i \neq j\) Show that every pairwise orthogonal family of non-zero vectors over \(\mathbb{R}\) is linearly independent.