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

Writing the given bases as $(u_1,\dots ,u_p)$ and $(v_1,\dots ,v_q)$, a basis of the Cartesian product with its componentwise vector space operations isThis is the direct sum basis. Therefore $\dim (W_1\times W_2)=p+q=\dim W_1+\dim W_2$. The construction includes zero-dimensional factors, whose corresponding portion of the basis is empty.

The intersection of vector subspaces $W_1\cap W_2$ contains zero, so $(0,0)\in U$. If $(u,-u),(v,-v)\in U$ and $a,b$ are scalars, thenbecause $au+bv\in W_1\cap W_2$ by the vector subspace conditions. These pairs belong to $W_1\times W_2$, since both $u$ and $-u$ belong to the required factors. Thus $U$ is a vector subspace of $W_1\times W_2$.

Define $f:W_1\cap W_2\to U$ by $f(u)=(u,-u)$. It is well-defined by the definition of $U$, andThus $f$ is a linear map. If $f(u)=f(v)$, comparing first components gives $u=v$, proving injectivity. Every element of $U$ has the form $(u,-u)=f(u)$, proving surjectivity. Hence $f$ is a linear isomorphism, with inverse $(u,-u)\mapsto u$, and $\dim U=\dim (W_1\cap W_2)$.

Every output $u_1+u_2$ lies in the sum of subspaces $W_1+W_2$, since it is a linear combination of members of the two vector subspaces. For $u=(u_1,u_2)$, $v=(v_1,v_2)$ and scalars $a,b$,Therefore $g$ is a linear map. Every vector in $W_1+W_2$ is such an output: group the terms of any linear combination from $W_1\cup W_2$ according to their originating vector subspace. Thus the addition map of subspaces is also surjective.

The kernel of a linear map $g$ is precisely $U$, sincePart (c) gives $\mathrm{im}g=W_1+W_2$. Apply the rank-nullity theorem to the finite-dimensional vector space $W_1\times W_2$, and then parts (a) and (b):This proves the dimension formula for a sum of subspaces. The kernel of a linear map records exactly the freedom to transfer a shared vector from one summand to the other without changing their sum.