Linear Algebra

Gaussian elimination first creates zeros below the diagonal. For a full matrix this costs about \(\frac{2}{3}n^{3}\) additions and multiplications, the source of the \(O(n^{3})\) option. An upper triangular matrix already has those zeros, so this phase has nothing to do, and only back substitution remains:

\(x_{i} = \dfrac{1}{a_{ii}}\Big(b_{i} - \sum_{j \gt i} a_{ij}x_{j}\Big)\) for \(i = n, n - 1, \dots, 1\).

Row \(i\) needs \(n - i\) multiplications and \(n - i\) additions, so the total is \(\frac{n(n-1)}{2}\) of each: \(O(n^{2})\). \(O(n)\) is too small, because each of the roughly \(\frac{n^{2}}{2}\) entries above the diagonal is used once.

Answer: B

Let \(e = (1, 1, \dots, 1)^{T}\). Each row of \(A\) sums to 1, so \(Ae = e\); then \(A^{2}e = e\) and \(A^{3}e = e\) as well. Hence

\[Be = A^{3}e - 2A^{2}e + Ae = e - 2e + e = 0.\]

(Equivalently, \(B = A(A - I)^{2}\) and \((A - I)e = 0\).) So \(Bx = 0\) has the non-zero solution \(e\), and every multiple \(ce\) solves it too: infinitely many solutions.

• A fails: \(x = 0\) always solves \(Bx = 0\).
• B is impossible: the solutions form a subspace, so there is exactly one solution or infinitely many.
• D fails: \(e \ne 0\) is a second solution.

Answer: C

• A and B: orthonormal bases are not unique. Rotating the standard basis gives another one; in \(\mathbb{R}^{2}\), \(\frac{1}{\sqrt{2}}(1, 1)\) and \(\frac{1}{\sqrt{2}}(1, -1)\) also form an orthonormal basis. Even changing the sign of one vector gives a new basis. So A is false and B is true.
• C is false: \((1, 0)\) and \((1, 1)\) are linearly independent, but they are not orthogonal and \((1, 1)\) is not a unit vector.
• D is true: if \(\sum_{i} c_{i}v_{i} = 0\) for orthonormal \(v_{i}\), taking the dot product with \(v_{j}\) leaves \(c_{j} = 0\), so every coefficient is zero.

Answer: B, D

Find the eigenvalues of \(A\) using \(x^{\top}x = 1\):

• \(Ax = x + x(x^{\top}x) = 2x\), so 2 is an eigenvalue.
• Any \(v\) orthogonal to \(x\) has \(x^{\top}v = 0\), so \(Av = v\). These vectors fill an \((n - 1)\)-dimensional subspace, so 1 is an eigenvalue of multiplicity \(n - 1\).

No eigenvalue is 0, so \(A\) is invertible with rank \(n\): A and B are true and C is false. The eigenvalues of \(A^{-1}\) are the reciprocals \(\frac{1}{2}\) and 1, all positive, so D is false.

Answer: A, B

The zero matrix and the identity both satisfy \(A^{3} = A\), and they rule out the first three options: \(A = 0\) is not invertible (A), \(A = I\) has determinant 1 (B), and \(A = 0\) has trace 0 (C).

For (D), multiplying by a matrix never increases rank, so \(\operatorname{rank}(A^{2}) \le \operatorname{rank}(A)\). Also \(A = A^{3} = A \cdot A^{2}\), so \(\operatorname{rank}(A) \le \operatorname{rank}(A^{2})\). The two ranks are therefore always equal.

Another view: \(A\) is diagonalisable with eigenvalues in \(\{-1, 0, 1\}\), and squaring keeps exactly the same eigenvalues non-zero.

Answer: D

Put the vectors in the columns of \(X = [x_1\ x_2\ \cdots\ x_n]\). Then \(A_{ij} = x_i^{\top} x_j\) says \(A = X^{\top} X\), a Gram matrix.

For any non-zero \(z\), \(z^{\top} A z = (Xz)^{\top}(Xz) = \|Xz\|^{2}\). The columns of \(X\) are linearly independent, so \(Xz \ne 0\) and \(z^{\top} A z \gt 0\). Hence \(A\) is positive definite, which rules out (D).

A positive definite matrix has only positive eigenvalues, so \(\det A = (\det X)^{2} \gt 0\) and \(A\) is invertible. Being symmetric, its singular values are these same positive eigenvalues, so 0 is not one of them. Options B and C fail.

Answer: A

Because the \(x_{i}\) are orthonormal, \(Ax_{j} = \sum_{i} x_{i}(x_{i}^{\top}x_{j}) = x_{j}\) for \(j = 1, \ldots, 5\), while \(Av = 0\) for every \(v\) orthogonal to all five. So \(A\) is the orthogonal projection onto their 5-dimensional span: it is symmetric, \(A^{2} = A\), and its eigenvalues are 1 (five times) and 0 (five times).

• A holds: the singular values of a symmetric matrix are the absolute values of its eigenvalues, and here the eigenvalues 0 and 1 are already non-negative.
• B holds: so the singular values are 0 or 1.
• C and D fail: 0 is an eigenvalue, so \(\det A = 0\) and \(A\) is not invertible.

Answer: A, B

Write the condition as \(x^{\top}(A^{\top}A - I)x = 0\) for every \(x\). The matrix \(A^{\top}A - I\) is symmetric, and a symmetric matrix whose quadratic form is zero for every \(x\) is the zero matrix. So \(A^{\top}A = I\), and \(A\) is orthogonal: A holds.

• D holds: \(A^{\top}A = I\) means \(A^{-1} = A^{\top}\) exists, so \(A\) has full rank.
• B fails: \(-I\), or any rotation, also preserves lengths.
• C fails: the rotation by 90\(^{\circ}\), \(\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}\), is orthogonal, but its eigenvalues are \(\pm i\). An orthogonal matrix only guarantees eigenvalues of modulus 1.

Answer: A, D

For a \(2 \times 2\) matrix the characteristic equation is \(\lambda^{2} - (\operatorname{tr}\boldsymbol{M})\lambda + \det \boldsymbol{M} = 0\). Here \(\operatorname{tr}\boldsymbol{M} = 2 + 1 = 3\) and \(\det \boldsymbol{M} = 2 \cdot 1 - (-1) \cdot 3 = 5\), so

\[\lambda^{2} - 3\lambda + 5 = 0, \qquad \lambda = \frac{3 \pm \sqrt{9 - 20}}{2} = \frac{3 \pm i\sqrt{11}}{2}.\]

The discriminant is negative, so the eigenvalues form a complex conjugate pair and none is real, which rules out (A), (C) and (D). A zero eigenvalue would also need \(\det \boldsymbol{M} = 0\).

Answer: B

Factor first: \(\boldsymbol{M}^{2} + 12\boldsymbol{M} = \boldsymbol{M}(\boldsymbol{M} + 12I)\), so its determinant is \(\det(\boldsymbol{M}) \cdot \det(\boldsymbol{M} + 12I)\).

Expanding along the first row,

\[\det(\boldsymbol{M}) = 1(6 - 9) - 2(18 - 12) + 3(9 - 4) = -3 - 12 + 15 = 0.\]

This is no accident: row 3 is the sum of rows 1 and 2, so \(\boldsymbol{M}\) is singular. A zero factor makes the whole product zero, so \(\det(\boldsymbol{M}^{2} + 12\boldsymbol{M}) = 0\) without computing \(\boldsymbol{M}^{2}\) at all.

Answer: 0