SEU-ML-Assign
作者:
Teddy van Jerry
最近上传:
3 年前
许可:
Other (as stated in the work)
摘要:
Southeast University Machine Learning Assignment template
\begin
Discover why over 20 million people worldwide trust Overleaf with their work.
\begin
Discover why over 20 million people worldwide trust Overleaf with their work.
%! TEX program = pdflatex
\documentclass[oneside,solution]{seu-ml-assign}
\title{Assignment}
\author{Teddy van Jerry}
\studentID{61520522}
\instructor{TeX - LaTeX Stack Exchange}
\date{\today}
\duedate{20:00 March 21, 2022}
\assignno{1}
\semester{SEU --- 2022 Spring}
\mainproblem{Linear Algreba}
\begin{document}
\maketitle
% \startsolution[print]
\problem{Basic Vector Operations}
\subproblem{}
$\|\mathbf{a}\|_2=\sqrt{1^2+2^2+3^2}=\sqrt{14},\quad \|\mathbf{b}\|_2=\sqrt{(-8)^2+1^2+2^2}=\sqrt{69}$.
\subproblem{}
$\|\mathbf{a}-\mathbf{b}\|_2=\sqrt{9^2+1^2+1^2}=\sqrt{83}$.
\subproblem{}
$\mathbf{a}$ and $\mathbf{b}$ are orthogonal.
\begin{proof}
The inner product of vectors $\mathbf{a}$ and $\mathbf{b}$ is
\begin{equation}
\langle\mathbf{a},\mathbf{b}\rangle=\mathbf{a}^T\mathbf{b}=1\times(-8)+2\times 1+3\times 2=0,
\end{equation}
therefore $\mathbf{a}$ and $\mathbf{b}$ are orthogonal.
\end{proof}
\problem{Basic Matrix Operations}
According to the consensus, the matrix notation should be the bold upper-case letter like $\mathbf{A}$ or $\bm{A}$, not $A$.
\subproblem{}
\begin{equation}
\begin{aligned}
[\mathbf{A}, \mathbf{I}_3]&=
\begin{bNiceArray}{rrr:rrr}
1&-3&3&1&0&0\\3&-5&3&0&1&0\\6&-6&4&0&0&1
\end{bNiceArray}\sim
\begin{bNiceArray}{rrr:rrr}
1&-3&3&1&0&0\\0&4&-6&-3&1&0\\0&12&-14&-6&0&1
\end{bNiceArray}\sim
\begin{bNiceArray}{rrr:rrr}
1&-3&3&1&0&0\\0&4&-6&-3&1&0\\0&0&4&3&-3&1
\end{bNiceArray}\\
&\sim
\begin{bNiceArray}{rrr:rrr}
1&-3&0&-\frac{5}{4}&\frac{9}{4}&\frac{3}{4}\\[0.3em]0&4&0&\frac{3}{2}&-\frac{7}{2}&-\frac{3}{2}\\[0.3em]0&0&1&\frac{3}{4}&-\frac{3}{4}&\frac{1}{4}
\end{bNiceArray}\sim
\begin{bNiceArray}{rrr:rrr}
1&0&0&-\frac{1}{8}&-\frac{3}{8}&\frac{3}{8}\\[0.3em]0&1&0&\frac{3}{8}&-\frac{7}{8}&\frac{3}{8}\\[0.3em]0&0&1&\frac{3}{4}&-\frac{3}{4}&\frac{1}{4}
\end{bNiceArray},
\end{aligned}
\end{equation}
where $\mathbf{I}_3$ is the $3\times 3$ identity matrix.
Therefore we have
\begin{equation}\label{eq:2-1-inv}
\mathbf{A}^{-1}=
\begin{bNiceArray}{rrr}
-\frac{1}{8}&-\frac{3}{8}&\frac{3}{8}\\[0.3em]\frac{3}{8}&-\frac{7}{8}&\frac{3}{8}\\[0.3em]\frac{3}{4}&-\frac{3}{4}&\frac{1}{4}
\end{bNiceArray}.
\end{equation}
The determinant of matrix $\mathbf{A}$ can be calculated as
\begin{equation}\label{eq:2-1-det}
\mathrm{det}(\mathbf{A})=1\times\begin{vNiceArray}{rr}
-5&3\\-6&4
\end{vNiceArray}-(-3)\times\begin{vNiceArray}{rr}
3&3\\6&4
\end{vNiceArray}+3\times\begin{vNiceArray}{rr}
3&-5\\6&-6
\end{vNiceArray}=1\times(-2)+3\times(-6)+3\times 12=16,
\end{equation}
where $|\cdot|$ denotes the determinant.
\subproblem{}
The rank of matrix $\mathbf{A}$ is $3$ because as is shown in Eq.~\eqref{eq:2-1-inv} the matrix $\mathbf{A}$ is invertible.
\subproblem{}
The trace of matrix $\mathbf{A}$ is
\begin{equation}
\mathrm{tr}(\mathbf{A})=\sum_{i=1}^{3}a_{ii}=1+(-5)+4=0.
\end{equation}
\begin{equation}
\mathbf{A}+\mathbf{A}^{T}=\begin{bNiceArray}{rrr}
1&-3&3\\3&-5&3\\6&-6&4
\end{bNiceArray}+
\begin{bNiceArray}{rrr}
1&3&6\\-3&-5&-6\\3&3&4
\end{bNiceArray}=
\begin{bNiceArray}{rrr}
2&0&9\\0&-10&-3\\9&-3&8
\end{bNiceArray}.
\end{equation}
\subproblem{}
\begin{equation}
\mathbf{A}+\mathbf{A}^{T}=\begin{bNiceArray}{rrr}
1&-3&3\\3&-5&3\\6&-6&4
\end{bNiceArray}+
\begin{bNiceArray}{rrr}
1&3&6\\-3&-5&-6\\3&3&4
\end{bNiceArray}=
\begin{bNiceArray}{rrr}
2&0&9\\0&-10&-3\\9&-3&8
\end{bNiceArray}.
\end{equation}
\subproblem{}
$\mathbf{A}$ is not an orthogonal matrix.
\begin{proof}
Assume $\mathbf{A}$ is an orthogonal matrix,
therefore
\begin{equation}
\mathbf{AA}^{T}=\mathbf{I}_3,
\end{equation}
Take the determinant at both side, it can be derived that
\begin{equation}
|\mathrm{det}(\mathbf{A})|=\sqrt{|\mathbf{A}||\mathbf{A}^T|}=|\mathrm{det}(\mathbf{I}_3)|=1,
\end{equation}
which contradicts with Eq.~\eqref{eq:2-1-det}.
Therefore, the assumption is false.
\end{proof}
\subproblem{}
Let $f(\lambda)$ be the characteristic function of matrix $\mathbf{A}$ and
\begin{equation}\label{eq:2-6-f}
f(\lambda)=\begin{vNiceArray}{ccc}
\lambda-1&3&-3\\-3&\lambda+5&-3\\-6&6&\lambda-4
\end{vNiceArray}=(\lambda-4)(\lambda+2)^2,
\end{equation}
therefore the eigenvalues are $\lambda_1=4, \lambda_2=\lambda_3=-2$.
Let the corresponding eigenvectors be $\bm{\alpha}_i$, $i=1,2,3$.
\begin{equation}
(\mathbf{A}-\lambda_i\mathbf{I}_3)\bm{\alpha}_i=\mathbf{0},\quad i=1,2,3,
\end{equation}
and the corresponding eigenvectors are
\begin{equation}
\bm{\alpha}_1=\begin{bNiceArray}{ccc}1&1&2\end{bNiceArray}^T,\quad
\bm{\alpha}_{2,3}=\begin{bNiceArray}{ccc}1&1+c_{2,3}&c_{2,3}\end{bNiceArray}^T,
\end{equation}
where $c_{2,3}\in\mathbb{R}$.
Without loss of generality, we take $c_2=0$ and $c_3=-1$, and we have $\bm{\alpha}_2=\begin{bNiceArray}{ccc}1&1&0\end{bNiceArray}^T$ and $\bm{\alpha}_2=\begin{bNiceArray}{ccc}1&0&-1\end{bNiceArray}^T$.
\subproblem{}
Use the result from Eq.~\eqref{eq:2-6-f}, the matrix $\mathbf{A}$ can be diagonalized as
\begin{equation}
\bm{\Lambda}=\begin{bNiceArray}{rrr}
4&0&0\\0&-2&0\\0&0&-2
\end{bNiceArray}.
\end{equation}
\subproblem{}
The $\ell_{2,1}$ norm of $\mathbf{A}$ is
\begin{equation}
\|\mathbf{A}\|_{2,1}=\sum_{i=1}^3\sqrt{\sum_{j=1}^3a_{ij}^2}=\sqrt{46}+\sqrt{70}+\sqrt{34}\approx 20.98,
\end{equation}
and the Frobenius norm of $\mathbf{A}$ is
\begin{equation}
\|\mathbf{A}\|_F=\sqrt{\sum_{i,j=1,\mathrlap{2,3}}a_{ij}^2}=\sqrt{150}=5\sqrt{6}\approx 12.247.
\end{equation}
\subproblem{}
The nuclear norm of $\mathbf{A}$ is
\begin{equation}
\|\mathbf{A}\|_*=\mathrm{tr}(\sqrt{\mathbf{A}\mathbf{A^*}})=\sum_{i=1}^3\sigma_i(\mathbf{A})\approx 14.728,
\end{equation}
and the spectral norm of $\mathbf{A}$ is
\begin{equation}
\|\mathbf{A}\|_2=\max\sigma_i(\mathbf{A})\approx 12.065.
\end{equation}
\vspace{2mm}
\begin{lstlisting}[language=Matlab, title={MATLAB Code for Check}]
A = [1, -3, 3; 3, -5, 3; 6, -6, 4]; % define the matrix A
inv(A) % calculate and print the inverse of A
det(A) % the determinant of A
rank(A) % the rank of A
trace(A) % the trace of A
A + A.' % the sum of A and the transpose of A
sum(sum(A * A.' ~= eye(3))) % check if A is orthogonal
[X, D] = eig(A) % the eigenvectors and the corresponding eigenvalues of A
sum(sqrt(sum(A .^ 2))) % l-2,1 norm of A
norm(A, 'fro') % Frobenius norm of A
sum(svd(A)) % nuclear norm of A
max(svd(A)) % spectral norm of A
\end{lstlisting}
\problem{Linear Equations}
\subproblem{}
It is evident to solve the linear equation
\begin{equation}\label{eq:3-1}
\left\{
\begin{aligned}
x_1&=-1, \\
x_2&=0, \\
x_3&=1.
\end{aligned}
\right.
\end{equation}
\subproblem{}
Let
\begin{equation}
\mathbf{A}=\begin{bNiceArray}{rrr}
2&2&3\\1&-1&0\\-1&2&1
\end{bNiceArray},\quad
\mathbf{b}=
\begin{bNiceArray}{r}
1\\-1\\2
\end{bNiceArray},
\end{equation}
and we have $\mathbf{Ax}=\mathbf{b}$ as
\begin{equation}
\begin{bNiceArray}{rrr}
2&2&3\\1&-1&0\\-1&2&1
\end{bNiceArray}
\begin{bNiceArray}{r}
x_1\\x_2\\x_3
\end{bNiceArray}=
\begin{bNiceArray}{r}
1\\-1\\2
\end{bNiceArray}.
\end{equation}
\subproblem{}
Since there is a unique solution shown in Eq.~\eqref{eq:3-1}, we know
\begin{equation}\label{eq:3-3}
\mathrm{rank}(\mathbf{A})=3.
\end{equation}
\subproblem{}
\begin{equation}
\begin{aligned}
[\mathbf{A}, \mathbf{I}_3]&=
\begin{bNiceArray}{rrr:rrr}
2&2&3&1&0&0\\1&-1&0&0&1&0\\-1&2&1&0&0&1
\end{bNiceArray}\sim
\begin{bNiceArray}{rrr:rrr}
2&2&3&1&0&0\\1&-1&0&0&1&0\\0&1&1&0&1&1
\end{bNiceArray}\sim
\begin{bNiceArray}{rrr:rrr}
1&1&\frac{3}{2}&\frac{1}{2}&0&0\\1&-1&0&0&1&0\\0&1&1&0&1&1
\end{bNiceArray}\\
&\sim
\begin{bNiceArray}{rrr:rrr}
1&1&\frac{3}{2}&\frac{1}{2}&0&0\\[0.3em]0&-2&-\frac{3}{2}&-\frac{1}{2}&1&0\\[0.3em]0&1&1&0&1&1
\end{bNiceArray}\sim
\begin{bNiceArray}{rrr:rrr}
1&1&\frac{3}{2}&\frac{1}{2}&0&0\\[0.3em]0&-1&-\frac{3}{4}&-\frac{1}{4}&\frac{1}{2}&0\\[0.3em]0&0&\frac{1}{4}&-\frac{1}{4}&\frac{3}{2}&1
\end{bNiceArray}\sim
\begin{bNiceArray}{rrr:rrr}
1&1&0&2&-9&-6\\[0.3em]0&-1&0&-1&5&3\\[0.3em]0&0&1&-1&6&4
\end{bNiceArray}\\
&\sim
\begin{bNiceArray}{rrr:rrr}
1&0&0&1&-4&-3\\0&1&0&1&-5&-3\\0&0&1&-1&6&4
\end{bNiceArray},
\end{aligned}
\end{equation}
therefore the inverse of $\mathbf{A}$ is
\begin{equation}\label{eq:3-4-inv}
\mathbf{A}^{-1}=\begin{bNiceArray}{rrr}
1&-4&-3\\1&-5&-3\\-1&6&4
\end{bNiceArray}.
\end{equation}
The determinant of $\mathbf{A}$ can be calculated as
\begin{equation}
\mathrm{det}(\mathbf{A})=2\times\begin{vNiceArray}{rr}
-1&0\\2&1
\end{vNiceArray}-2\times\begin{vNiceArray}{rr}
1&0\\-1&1
\end{vNiceArray}+3\times\begin{vNiceArray}{rr}
1&-1\\-1&2
\end{vNiceArray}=2\times(-1)-2\times 1+3\times 1=-1.
\end{equation}
\subproblem{}
As is shown in Eq.~\eqref{eq:3-3}, $\mathbf{A}$ is invertible and with the result in Eq.~\eqref{eq:3-4-inv}
\begin{equation}
\mathbf{x}=\mathbf{A}^{-1}\mathbf{b}=
\begin{bNiceArray}{rrr}
1&-4&-3\\1&-5&-3\\-1&6&4
\end{bNiceArray}
\begin{bNiceArray}{r}
1\\-1\\2
\end{bNiceArray}=
\begin{bNiceArray}{r}
-1\\0\\1
\end{bNiceArray},
\end{equation}
and it is exactly the same result with Eq.~\eqref{eq:3-1}.
\subproblem{}
The inner product
\begin{equation}
\langle\mathbf{x},\mathbf{b}\rangle=\mathbf{x}^T\mathbf{b}=1\times 1+0\times(-1)+1\times 2=1,
\end{equation}
and the outer product is
\begin{equation}
\mathbf{x}\otimes\mathbf{b}=\mathbf{x}\mathbf{b}^T=
\begin{bNiceArray}{r}
-1\\0\\1
\end{bNiceArray}
\begin{bNiceArray}{rrr}
1&-1&2
\end{bNiceArray}=
\begin{bNiceArray}{rrr}
-1&1&-2\\0&0&0\\1&-1&2
\end{bNiceArray}.
\end{equation}
\subproblem{}
$\|\mathbf{b}\|_1=|1|+|-1|+|2|=4,\quad\|\mathbf{b}\|_2=\sqrt{1^2+(-1)^2+2^2}=\sqrt{6},\quad\|\mathbf{b}\|_{\infty}=\max\{|1|,|-1|,|2|\}=2.$
\subproblem{}
Let $\mathbf{y}=\begin{bNiceArray}{rrr}
y_1&y_2&y_3
\end{bNiceArray}^T$,
we have
\begin{equation}
\mathbf{y}^T\mathbf{Ay}=
\begin{bNiceArray}{rrr}
y_1&y_2&y_3
\end{bNiceArray}
\begin{bNiceArray}{rrr}
2&2&3\\1&-1&0\\-1&2&1
\end{bNiceArray}
\begin{bNiceArray}{r}
y_1\\y_2\\y_3
\end{bNiceArray}=2y_1^2-y_2^2+y_3^2+3y_1y_2+2y_2y_3+2y_1y_3,
\end{equation}
and
\begin{equation}
\bigtriangledown_{\mathbf{y}}\mathbf{y}^T\mathbf{Ay}=
\begin{bNiceArray}{r}
\frac{\partial}{\partial y_1}\mathbf{y}^T\mathbf{Ay} \\[.3em]
\frac{\partial}{\partial y_2}\mathbf{y}^T\mathbf{Ay} \\[.3em]
\frac{\partial}{\partial y_3}\mathbf{y}^T\mathbf{Ay}
\end{bNiceArray}=
\begin{bNiceArray}{r}
4y_1+3y_2+2y_3 \\
3y_1-2y_2+2y_3 \\
2y_1+2y_2+2y_3
\end{bNiceArray}.
\end{equation}
\subproblem{}
The equation $\mathbf{A}_1\mathbf{x}=\mathbf{b}_1$ can be represented as
\begin{equation}
\begin{bNiceArray}{rrr}
2&2&3\\1&-1&0\\-1&2&1\\-1&2&1
\end{bNiceArray}
\begin{bNiceArray}{r}
x_1\\x_2\\x_3
\end{bNiceArray}=
\begin{bNiceArray}{r}
1\\-1\\2\\2
\end{bNiceArray}.
\end{equation}
\subproblem{}
$\mathrm{rank}(\mathbf{A}_1)=3$.
\begin{proof}
On one hand, $\mathrm{rank}(\mathbf{A}_1)\geq\mathrm{rank}(\mathbf{A})=3$ which is shown in Eq.~\eqref{eq:3-3}.
On the other hand, $\mathrm{rank}(\mathbf{A}_1)\leq\min\{3,4\}=3$.
Therefore, $\mathrm{rank}(\mathbf{A}_1)=3$.
We can also find the first three equations are linearly independent while the last equation is actually the same with the third equation which makes it meaningless.
\end{proof}
\subproblem{}
Yes.
\begin{proof}
Since $\mathrm{rank}(\mathbf{A}_1)=\|\mathbf{x}\|_0$, i.e. rank of $\mathbf{A}_1$ is equal to the dimension of $\mathbf{x}$, the formula can be solved with a unique solution the same as Eq.~\eqref{eq:3-1}.
\end{proof}
\end{document}