Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 4

For the equal-cardinality basis criterion, because $S$ spans $V$, repeatedly remove a vector whenever it is a linear combination of the others. Such a removal does not change the span. The finite process ends with a linearly independent spanning subset $T$, hence a basis of $V$.

If the original $S$ were linearly dependent, at least one removal would occur and $|T|<n$. But a basis of an $n$-dimensional vector space has $n$ vectors. Equivalently, apply the allowed claim to the basis $T$ and any fixed $n$-vector basis of $V$: the latter would wrongly be linearly dependent. Thus no removal was possible. The original spanning set is linearly independent and therefore a basis.

Suppose a vector $v$ lies outside the span of $S$. Then $S\cup \{v\}$ is linearly independent: in an equation $\alpha v+{\sum }_i{\beta }_i{s}_i=0$, a nonzero $\alpha$ would express $v$ in that span, and with $\alpha =0$ the independence of $S$ forces every ${\beta }_i=0$.

This would give $n+1$ linearly independent vectors in a space with an $n$-vector basis, contrary to the supplied claim. Therefore $S$ spans $V$. Independence plus spanning makes $S$ a basis.

The product $AB$ is $m\times p$, so multiplying it by the $p\times q$ matrix $C$ gives an $m\times q$ matrix. The product $BC$ is $n\times q$, so multiplying it on the left by the $m\times n$ matrix $A$ also gives an $m\times q$ matrix. Both multiplications have matching inner dimensions.

For the specified row and column, expand the two matrix products and reorder only finite sums:The middle equality uses scalar associativity and distributivity, and the interchange of two finite sums. Together with their equal dimensions, equality of every entry proves $(AB)C=A(BC)$.

Eliminate the first column using multipliers $3$ and $2$. The two residual rows have second entries zero and four, so interchange their order for the next pivot. One resulting Pivoted LU decomposition isThe factors below the first pivot must follow the permuted row order, which is why $L$ contains $2$ before $3$. Direct multiplication gives rows $(3,1,4)$, $(6,6,6)$ and $(9,3,1)$ in both $PA$ and $LU$. This checks the permutation convention rather than confusing $PA=LU$ with a different placement of $P$.

Apply the same permutation to the right-hand side and solve two triangular systems. Forward substitution in $Ly=Pb$ givesso $y=(3,-6,-11{)}^T$. Back substitution in $Ux=y$ gives $-11x_3=-11$, $4x_2-2x_3=-6$, and $3x_1+x_2+4x_3=3$. Therefore $x=(0,-1,1{)}^T$. Substitution in the original system returns $(3,-2,0{)}^T$, as required.

A triangular matrix has determinant equal to the product of its diagonal entries, so $\det L=1$ and $\det U=3\cdot 4\cdot (-11)=-132$. A permutation matrix exchanging two rows has determinant $-1$. Using multiplicativity of the determinant in $PA=LU$ yields $(-1)\det A=-132$. Hence $\det A=132$.