%! 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}