Problem 1. To find dimension, first and foremost, one needs to construct/find a basis. Since \begin{equation}
\label{use this again}
\matrixx{
1&2&-2&3\\
2&4&-3&4\\
5&10&-8&11
}\to \cdots\to
\matrixx{
1&2&0&-1\\
0&0&1&-2\\
0&0&0&0
},
\end{equation} we have \[
Ax=0\iff \begin{cases}
x_1=x_4-2x_2\\
x_3=2x_4
\end{cases}
\iff x=x_2\matrixx{-2\\1\\0\\0}
+x_4\matrixx{
1\\0\\2\\1
},
\] thus $\nul A=\spann\left\{\matrixx{-2\\1\\0\\0},\matrixx{
1\\0\\2\\1
}\right\}$. Since $\matrixx{-2\\1\\0\\0}$ and $\matrixx{
1\\0\\2\\1
}$ are linearly independent, we have \[\boxed{\dim \nul A=2}.
\]
Problem 2. Here is a usual theorem to determine which columns of a matrix form a basis of the column space.
Theorem. Let $A=\matrixx{a_1&a_2&\cdots &a_n}$, where $a_i\in \R^m$. If $i_1,i_2,\dots,i_k$th columns ($i_1<i_2<\cdots<i_k$) of the row echelon form of $A$ are pivot columns, then $\{a_{i_1},a_{i_2},\dots,a_{i_k}\}$ is a basis of $\col A$.For a proof, see the bottom of this post. Note that the number $k$ is the dimension of $\col A$ and the number of pivot columns, hence
$\dim \col A=$ number of pivots of echelon form of $A$.
By (\ref{use this again}) since the first and the third columns of the echelon form are pivotal, $a_1=\matrixx{1\\2\\5}$ and $a_3=\matrixx{-2\\-3\\-8}$ form a basis of $\col A$, hence $\dim \col A =2$.
Remark. The theorem stated in problem 2 will be helpful in the determination of geometric multiplicity of eigenvalues later.
Problem 3. This problem follows from the nullity-rank theorem:
Theorem (Nullity-Rank). Let $A$ be an $m\times n$ real matrix, then \[Later we will need the following generalization in this course:
n=\underbrace{\dim \nul A}_\text{nullity} +\underbrace{\dim \col A}_\text{rank}.
\]
Theorem (Generalized Nullity-Rank). Let $T:V\to W$ be linear between vector spaces $V$ and $W$, $\dim V<\infty$, then \[Note that LHS is always the dimension of the domain. Now we are going to prove the chain \[
\dim V = \dim \ker T+\dim \range T.
\]
(c)\implies (a)\implies (b)\implies (c).
\] $(c)\Rightarrow (a)$: Since $A$ is invertible $\iff$ $A$ is $1-1$ and onto, hence (a) follows.
$(a)\Rightarrow (b)$: Assume $A$ is injective, then equivalently, $\nul A=\{0\}$, hence by nullity-rank theorem, \[
n=0+\dim \col A,
\] hence $\dim \col A=n$ and $\col A\subseteq \R^n$, by problem 4 of tutorial note 5, $\col A=\R^n$, showing that $A$ is surjective.
$(b)\Rightarrow (c)$: Assume $A$ is surjective, then $\col A=\R^n$, by nullity-rank theorem again, \[
n=\dim \nul A + \dim \col A=\dim \nul A + n,
\] and thus $\dim \nul A=0$, i.e., $\nul A=\{0\}$, so $A$ is injective. Together with assumption (b), $A$ is invertible, thus (c) follows.
Remark. For an $m\times n$ matrix $A$, we say that $A$ is of full rank if it attains its maximum possible rank among all $m\times n$ matrices. For instance, when a matrix is thin (i.e., $m\ge n$), by nullity rank theorem, $\dim \col A=n-\dim \nul A\leq n$, hence maximum possible rank is attained when $\dim\nul A=0$, i.e., $A$ is injective. Hence
A thin matrix $A$ is of full rank $\iff$ $A$ is 1-1.
Next, when $A$ is strictly fat (i.e., $m< n$), then $A$ (as a map $\R^n\to \R^m$) can never be injective, the argument above fails. Note that $\col A$ is a subspace of $\R^m$, so the maximum possible rank is $m$, namely, this happens when $A$ is surjective. Thus
A strictly fat matrix $A$ is of full rank $\iff$ $A$ is onto.
Remark. The result in problem 3 can be extended to any linear transformation $T:V\to W$, with $\boxed{\dim V=\dim W<\infty}$ using the same proof. i.e.,
$T$ is 1-1 $\iff$ $T$ is onto $\iff$ $T$ is invertible.
This is a magical tool since invertibility is the same as injectivity and the latter is much easier to show.Remark. When $\dim V=\infty$, the result in problem 3 cannot be extended to any $T:V\to V$. In particular, consider \[V=\R^\infty:=\{(a_1,a_2,a_3,\dots):a_1,a_2,a_3,\dots\in \R\},\] the map $T:V\to V$ defined by $(a_1,a_2,\dots)\mapsto (0,a_1,a_2,\dots)$ is injective but not surjective. Hence when $V$ is infinite dimensional, for linear $T:V\to V$,
$T$ 1-1 $\iff$ $T$ onto
is not true in general.Problem 4. Since $I+S$ is also square, we can apply problem 3. Note that
$I+S$ is invertible $\iff$ $I+S$ is injective $\iff$ ($(I+S)x=0\implies x=0$).
Now we try to show the last statement.
Let $(I+S)x=0$, then $Sx=-x$. Define $\inner{a,b}=a\cdot b$, where $a,b\in \R^n$ and $a\cdot b$ means the dot product between $a$ and $b$. For $x\in \R^n$, recall that $\|x\|^2=\inner{x,x}$, and also for any $n\times n$ matrix $A$,\[
\inner{Ax,y}=(Ax)^Ty=x^T(A^Ty)=\inner{x,A^Ty},\quad x,y\in \R^n
\] hence \begin{equation}\label{come here}
\|x\|^2=\inner{x,x}=\inner{-Sx,x}= - \inner{Sx,x}
\end{equation} and \[
\inner{Sx,x}=\inner{x,S^Tx}=\inner{x,(-S)x}=-\inner{x,Sx}=-\inner{Sx,x},
\] hence $2\inner{Sx,x}=0$, i.e., $\inner{Sx,x}=0$. Continuing from (\ref{come here}), $\|x\|=0$, so $x=0$, as desired. We conclude that $I+S$ is injective, hence invertible.
Problem 5. Observe that $\nul B\subseteq \nul AB$ since $Bx=0\implies ABx=0$. This observation is a starting point. Let $k=\dim \nul B$, and let $\{v_1,\dots,v_k\}$ be a basis of $\nul B$. Extend it to a basis of $\nul AB$: $\{u_1,\dots,u_h,v_1,\dots,v_k\}$. Then \[
\dim \nul AB=h+k=h+\dim \nul B.
\] We need to study $h$, to do this, note that $ABu_1=ABu_2=\cdots=ABu_h=0$, hence \begin{equation}\label{set inclusion}
\{Bu_1,Bu_2,\dots,Bu_h\}\subseteq \nul A.
\end{equation} We cannot say $h\leq \dim \nul A$ at the moment, this prompts us to study whether $\{Bu_1,Bu_2,\dots,Bu_h\}$ is linearly independent. To check this, let $a_i\in \R$ be such that \[
0=\sum_{i=1}^h a_iBu_i=B\brac{\sum_{i=1}^h a_iu_i},
\] then $\sum_{i=1}^h a_iu_i\in \nul B$. Since $\{v_1,\dots,v_k\}$ is a basis of $\nul B$, there are $b_i\in \R$ such that \[
\sum_{i=1}^h a_iu_i=\sum_{j=1}^k b_iv_i\iff \sum_{i=1}^h a_iu_i+\sum_{j=1}^k (-b_i)v_i=0,
\] however, $\{u_1,\dots,h_h,v_1,\dots,v_k\}$ is linearly independent, hence $a_1=a_2=\cdots=a_h=0$, as desired. Hence from (\ref{set inclusion}) we conclude \[
h\leq \dim \nul A.
\]
Problem 6. Easy to show $\dim \nul A=2$, hence by nullity-rank theorem we have \[
4=\dim \nul A+\dim \col A= 2+\dim \col A,
\] hence $\dim \col A=2$ (recall that LHS is the dimension of the domain). As $\col A\subseteq \R^2$, we have $\col A=\R^2$, hence $A$ is surjective.
\inner{Ax,y}=(Ax)^Ty=x^T(A^Ty)=\inner{x,A^Ty},\quad x,y\in \R^n
\] hence \begin{equation}\label{come here}
\|x\|^2=\inner{x,x}=\inner{-Sx,x}= - \inner{Sx,x}
\end{equation} and \[
\inner{Sx,x}=\inner{x,S^Tx}=\inner{x,(-S)x}=-\inner{x,Sx}=-\inner{Sx,x},
\] hence $2\inner{Sx,x}=0$, i.e., $\inner{Sx,x}=0$. Continuing from (\ref{come here}), $\|x\|=0$, so $x=0$, as desired. We conclude that $I+S$ is injective, hence invertible.
Follow-up Practice. Show that for any real matrix $A$, $I+A^TA$ is invertible.
Problem 5. Observe that $\nul B\subseteq \nul AB$ since $Bx=0\implies ABx=0$. This observation is a starting point. Let $k=\dim \nul B$, and let $\{v_1,\dots,v_k\}$ be a basis of $\nul B$. Extend it to a basis of $\nul AB$: $\{u_1,\dots,u_h,v_1,\dots,v_k\}$. Then \[
\dim \nul AB=h+k=h+\dim \nul B.
\] We need to study $h$, to do this, note that $ABu_1=ABu_2=\cdots=ABu_h=0$, hence \begin{equation}\label{set inclusion}
\{Bu_1,Bu_2,\dots,Bu_h\}\subseteq \nul A.
\end{equation} We cannot say $h\leq \dim \nul A$ at the moment, this prompts us to study whether $\{Bu_1,Bu_2,\dots,Bu_h\}$ is linearly independent. To check this, let $a_i\in \R$ be such that \[
0=\sum_{i=1}^h a_iBu_i=B\brac{\sum_{i=1}^h a_iu_i},
\] then $\sum_{i=1}^h a_iu_i\in \nul B$. Since $\{v_1,\dots,v_k\}$ is a basis of $\nul B$, there are $b_i\in \R$ such that \[
\sum_{i=1}^h a_iu_i=\sum_{j=1}^k b_iv_i\iff \sum_{i=1}^h a_iu_i+\sum_{j=1}^k (-b_i)v_i=0,
\] however, $\{u_1,\dots,h_h,v_1,\dots,v_k\}$ is linearly independent, hence $a_1=a_2=\cdots=a_h=0$, as desired. Hence from (\ref{set inclusion}) we conclude \[
h\leq \dim \nul A.
\]
Follow-up Practice. Let $U$ and $V$ be two finite dimensional subspaces of some vector space. Given that $U+V:=\{u+v:u\in U,v\in V\}$ is a vector space, show that \[
\dim (U+V)\leq \dim U+\dim V.
\]
\dim (U+V)\leq \dim U+\dim V.
\]
Problem 6. Easy to show $\dim \nul A=2$, hence by nullity-rank theorem we have \[
4=\dim \nul A+\dim \col A= 2+\dim \col A,
\] hence $\dim \col A=2$ (recall that LHS is the dimension of the domain). As $\col A\subseteq \R^2$, we have $\col A=\R^2$, hence $A$ is surjective.
Proof of theorem in problem 2. Let $A=\matrixx{a_1&a_2&\cdots &a_n}$, $a_i\in \R^m$. We let $E$ be the product of elementary matrices such that $EA$ is in reduced echelon form. Suppose $i_1,i_2,\dots,i_k$th columns (with $i_1<i_2<\cdots<i_k$) of $EA$ are pivot columns, then \[
Ea_{i_1}=e_1,Ea_{i_2}=e_2,\dots,Ea_{i_k}=e_k.
\] It is easy to see that $a_{i_1},\dots,a_{i_k}$ are linearly independent. Now we show that every columns in $A$ is in the span of $\{a_{i_j}:j=1,2,\dots,k\}$. Indeed, for $p=1,2,\dots,n$, \[
Ea_p=\sum_{j=1}^k b_j e_j = \sum_{j=1}^k b_j Ea_{i_j}
\]and hence \[
a_p=\sum_{j=1}^k b_ja_{i_j}.
\] Since each columns of $A$ is in the span of $\{a_{i_j}:j=1,2,\dots,k\}$, thus \[\col A=\spann \{a_{i_j}:j=1,2,\dots,k\}.\qed\]
Remark. In some text $\rank (A)=\dim \col A$ is called the column rank of $A$. On the other hand, the dimensional of the "row space" (i.e., the space spanned by rows of $A$: $\col A^T$) is called the row rank of $A$. In fact they are the same:
Theorem. Let $A=\matrixx{a_1&\cdots&a_n}$ be an $m\times n$ matrix, then \[Proof. Let $E$ and $\{a_{i_j}:j=1,2,\dots,k\}$ be defined as in the proof above, i.e., $EA$ is in reduce row echelon form and $i_1,i_2,\dots,i_k$ columns ($i_1<i_2<\cdots<i_k$) of $EA$ are pivotal, then $\rank (A)=k$. On the other hand, $(EA)^T=A^TE^T$ and $\col (A^TE^T)=\col (A^T)$, so \[
\rank A=\rank A^T.
\]
\dim \col A^T=\dim \col (A^TE^T)=\dim \col (EA)^T.
\] Since $EA$ is the reduced row echelon form of $A$, only the first $k$ rows are nonzero, hence $\col (EA)^T$ is spanned by first $k$ columns of $(EA)^T$ which are linearly independent, thus $\dim \col A^T=k$. This establishes the equality $\rank A=\rank A^T$.$\qed$
No comments:
Post a Comment