\documentclass[a4paper]{article}

\usepackage{fancyhdr}
\usepackage{extramarks}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage[plain]{algorithm}
\usepackage{algpseudocode}
\usepackage{enumitem}
\usepackage{framed}
\usepackage{multicol}

\graphicspath{ {./images/} }

\usetikzlibrary{automata,positioning}

%
% Basic Document Settings
%

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1}

\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkClass\ : \hmwkTitle}
\rhead{\firstxmark}
\lfoot{\lastxmark}
\cfoot{\thepage}

\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}

\setlength\parindent{0pt}

%
% Create Problem Sections
%

\newcommand{\enterProblemHeader}[1]{
    \nobreak\extramarks{}{Question \arabic{#1} continued on next page\ldots}\nobreak{}
    \nobreak\extramarks{Question \arabic{#1} (continued)}{Question \arabic{#1} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitProblemHeader}[1]{
    \nobreak\extramarks{Question \arabic{#1} (continued)}{Question \arabic{#1} continued on next page\ldots}\nobreak{}
    \stepcounter{#1}
    \nobreak\extramarks{Question \arabic{#1}}{}\nobreak{}
}

\setcounter{secnumdepth}{0}
\newcounter{partCounter}
\newcounter{homeworkProblemCounter}
\setcounter{homeworkProblemCounter}{1}
\nobreak\extramarks{Question \arabic{homeworkProblemCounter}}{}\nobreak{}

\newenvironment{homeworkProblem}[1][-1]{
    \ifnum#1>0
        \setcounter{homeworkProblemCounter}{#1}
    \fi
    \section{Question \arabic{homeworkProblemCounter}}
    \setcounter{partCounter}{1}
    \enterProblemHeader{homeworkProblemCounter}
}{
    \exitProblemHeader{homeworkProblemCounter}
}

\newcommand{\hmwkClass}{INF 1004 Mathematics 2}
\newcommand{\hmwkTitle}{Tutorial\ \#11}
\newcommand{\hmwkAuthorName}{\textbf{Woon Jun Wei}}
\newcommand{\hmwkStudentID}{\textbf{2200624}}

\title{
    \vspace{2in}
    \textmd{\textbf{\hmwkClass \\ \hmwkTitle}}\\
    \vspace{3in}
}

\author{\hmwkAuthorName \\ \hmwkStudentID}
\date{\today}

\renewcommand{\part}[1]{\textbf{\large Part \arabic{partCounter}}\stepcounter{partCounter}\\}

%
% Various Helper Commands
%

% Useful for algorithms
\newcommand{\alg}[1]{\textsc{\bfseries \footnotesize #1}}

% For derivatives
\newcommand{\deriv}[1]{\frac{\mathrm{d}}{\mathrm{d}x} (#1)}

% For partial derivatives
\newcommand{\pderiv}[2]{\frac{\partial}{\partial #1} (#2)}

% Integral dx
\newcommand{\dx}{\mathrm{d}x}

% Alias for the Solution section header
\newcommand{\solution}{\textbf{\large My Solution\\}}
\newcommand{\answer}{\textbf{\large Sample Solutions\\}}

% Probability commands: Expectation, Variance, Covariance, Bias
\newcommand{\E}{\mathrm{E}}
\newcommand{\Var}{\mathrm{Var}}
\newcommand{\Cov}{\mathrm{Cov}}
\newcommand{\Bias}{\mathrm{Bias}}

\def\therefore{\boldsymbol{\text{ }
\leavevmode
\lower0.4ex\hbox{$\cdot$}
\kern-.5em\raise0.7ex\hbox{$\cdot$}
\kern-0.55em\lower0.4ex\hbox{$\cdot$}
\thinspace\text{ }}}

\begin{document}

\maketitle

\pagebreak

\begin{homeworkProblem}
    \begin{itemize}
        \item Compute the eigenvalues and eigenvectors for the matrices below.
        \item For one of these matrices compute the matrix $P$ such that $P^{-1}DP = A$, and verify that $PAP^{-1}$ is the diagonal matrix of the eigenvalues
    \end{itemize}

    $$
    \begin{align*}
        A &= \begin{bmatrix} 4&\sqrt{15}\\\sqrt{15}&2 \end{bmatrix} \\
        A &= \begin{bmatrix} 2&-2\\-3&1 \end{bmatrix} \\
        A &= \begin{bmatrix} 2&-4\\4&-6 \end{bmatrix} \\
    \end{align*}
    $$

    \solution

    \pagebreak

    \part 
            
    $$
        A = \begin{bmatrix} 4&\sqrt{15}\\\sqrt{15}&2 \end{bmatrix} 
    $$

    $$
    \det{\begin{bmatrix} 4-\lambda&\sqrt{15}\\\sqrt{15}&2-\lambda \end{bmatrix}} = 0
    $$

    $$
    \begin{align*}
        f(\lambda) &= \lambda^2 - 6\lambda -7 = 0\\
                   &(\lambda - 7)(\lambda + 1) = 0\\
        \lambda &= 7, -1
    \end{align*}
    $$
    
    \begin{multicols}{2}
    $$
    \begin{align*}
        \lambda_1 &= -1,\\
        A-(-1)I &= \begin{bmatrix} 5&\sqrt{15}\\\sqrt{15}&3 \end{bmatrix} \\
                &= \begin{bmatrix} \sqrt{15} & 3\\0&0\end{bmatrix} \\
                \sqrt{15}x_0+3x_1 &= 0\\
                x_0 &= -\frac{3}{\sqrt{15}}x_1\\
                \begin{bmatrix}x_0\\x_1\end{bmatrix} &= x_1\begin{bmatrix}-\frac{3}{\sqrt{15}}\\1\end{bmatrix}\\
                \therefore v_1 &= \begin{bmatrix}-3\\\sqrt{15}\end{bmatrix}
    \end{align*}
    $$
    
    \columnbreak

    $$
    \begin{align*}
        \lambda_1 &= 7,\\
        A-(7)I &= \begin{bmatrix} -3&\sqrt{15}\\\sqrt{15}&-5 \end{bmatrix} \\
                &= \begin{bmatrix} \sqrt{15} & -5\\0&0\end{bmatrix} \\
                \sqrt{15}x_0-5x_1 &= 0\\
                x_0 &= \frac{5}{\sqrt{15}}x_1\\
                \begin{bmatrix}x_0\\x_1\end{bmatrix} &= x_1\begin{bmatrix}\frac{5}{\sqrt{15}}\\1\end{bmatrix}\\
                \therefore v_1 &= \begin{bmatrix}5\\\sqrt{15}\end{bmatrix}
    \end{align*}
    $$

    \end{multicols}

    Case: Symmetric Matix, 2 different eigenvalues, 2 eigenvectors\\
    Eigenspaces are orthogonal, Check: $v_0\cdotv_1 = -15 + \sqrt{15}\sqrt{15} = 0$\\


    \textbf{Eigendecomposition}\\

    $\lambda_1=-1, v_1 = \begin{bmatrix}-3\\\sqrt{15}\end{bmatrix}, \qquad \lambda_2=7, v_2 = \begin{bmatrix}5\\\sqrt{15}\end{bmatrix}$\\

    $p^{-1} = \begin{bmatrix}v_1&v_2\end{bmatrix} = \begin{bmatrix}-3&5\\\sqrt{15}&\sqrt{15}\end{bmatrix}$\\
    $D = \begin{bmatrix}-1&0\\0&7\end{bmatrix}$\\
    $p = (p^{-1})^{-1} = \frac{1}{-3\sqrt{15}-5\sqrt{15}} \begin{bmatrix}\sqrt{15}&-5\\-\sqrt{15}&-3\end{bmatrix} = \begin{bmatrix}-\frac{1}{8}&\frac{5}{8\sqrt{15}}\\\frac{1}{8}&\frac{3}{8\sqrt{15}}\end{bmatrix}$\\
    Verify:
    $$
    \begin{align*}
        P^{-1}DP = \begin{bmatrix}-3&5\\\sqrt{15}&\sqrt{15}\end{bmatrix}\begin{bmatrix}-1&0\\0&7\end{bmatrix}\begin{bmatrix}-\frac{1}{8}&\frac{5}{8\sqrt{15}}\\\frac{1}{8}&\frac{3}{8\sqrt{15}}\end{bmatrix} = \begin{bmatrix}4&\sqrt{15}\\\sqrt{15}&2\end{bmatrix} = A\\
        PAP^{-1} = \begin{bmatrix}-\frac{1}{8}&\frac{5}{8\sqrt{15}}\\\frac{1}{8}&\frac{3}{8\sqrt{15}}\end{bmatrix}\begin{bmatrix}4&\sqrt{15}\\\sqrt{15}&2\end{bmatrix}\begin{bmatrix}-\frac{1}{8}&\frac{5}{8\sqrt{15}}\\\frac{1}{8}&\frac{3}{8\sqrt{15}}\end{bmatrix} = \begin{bmatrix}-1&0\\0&7\end{bmatrix} = D
    \end{align*}
    $$

    \pagebreak 

    \part 

    $$
        A = \begin{bmatrix} 2&-2\\-3&1 \end{bmatrix}
    $$

    $$
    \det{\begin{bmatrix} 2-\lambda&-2\\-3&1-\lambda \end{bmatrix}} = 0
    $$

    $$
    \begin{align*}
        f(\lambda) &= \lambda^2 - 3\lambda - 4 = 0\\
                   &(\lambda - 4)(\lambda + 1) = 0\\
        \therefore \lambda &= 4, -1
    \end{align*}
    $$

    \begin{multicols}{2}

    $$
    \begin{align*}
        \lambda_1 &= -1,\\
        A-(-1)I &= \begin{bmatrix} 3&-2\\-3&2 \end{bmatrix} \\
                &= \begin{bmatrix} 3 & -2\\0&0\end{bmatrix} \\
                3x_0-2x_1 &= 0\\
                x_0 &= \frac{2}{3}x_1\\
                \begin{bmatrix}x_0\\x_1\end{bmatrix} &= x_1\begin{bmatrix}\frac{2}{3}\\1\end{bmatrix}\\
                \therefore v_1 &= \begin{bmatrix}2\\3\end{bmatrix}
    \end{align*}
    $$

    \columnbreak

    $$
    \begin{align*}
        \lambda_2 &= 4,\\
        A-(4)I &= \begin{bmatrix} -2&-2\\-3&-3 \end{bmatrix} \\
                &= \begin{bmatrix} -2 & -2\\0&0\end{bmatrix} \\
                -2x_0-2x_1 &= 0\\
                x_0 &= -x_1\\
                \begin{bmatrix}x_0\\x_1\end{bmatrix} &= x_1\begin{bmatrix}-1\\1\end{bmatrix}\\
                \therefore v_2 &= \begin{bmatrix}1\\-1\end{bmatrix}
    \end{align*}
    $$
    \end{multicols}

    Eigenspaces are not orthogonal, but matrix is not symetric\\
    So even though we get 2 eigenvalues and 2 eigenvectors, it is okay that the eigenvectors are not orthogonal to each other.\\

    \textbf{Eigendecomposition}\\

    $\lambda_1=-1, v_1 = \begin{bmatrix}2\\3\end{bmatrix}, \qquad \lambda_2=4, v_2 = \begin{bmatrix}1\\-1\end{bmatrix}$\\

    $p^{-1} = \begin{bmatrix}v_1&v_2\end{bmatrix} = \begin{bmatrix}2&1\\3&-1\end{bmatrix}$\\

    $D = \begin{bmatrix}-1&0\\0&4\end{bmatrix}$\\

    $p = (p^{-1})^{-1} = \frac{1}{-2-3} \begin{bmatrix}-1&-1\\-3&2\end{bmatrix} = \begin{bmatrix}\frac{1}{5}&\frac{1}{5}\\\frac{3}{5}&-\frac{2}{5}\end{bmatrix}$\\

    $$
    \begin{align*}
        P^{-1}DP &= \begin{bmatrix}2&1\\3&-1\end{bmatrix}\begin{bmatrix}-1&0\\0&4\end{bmatrix}\begin{bmatrix}\frac{1}{5}&\frac{1}{5}\\\frac{3}{5}&-\frac{2}{5}\end{bmatrix} = \begin{bmatrix}2&-2\\-3&1\end{bmatrix} = A\\
        PAP^{-1} &= \begin{bmatrix}\frac{1}{5}&\frac{1}{5}\\\frac{3}{5}&-\frac{2}{5}\end{bmatrix}\begin{bmatrix}2&-2\\-3&1\end{bmatrix}\begin{bmatrix}2&1\\3&-1\end{bmatrix} = \begin{bmatrix}-1&0\\0&4\end{bmatrix} = D
    \end{align*}
    $$

    \pagebreak 

    \part 

    $$
    A = \begin{bmatrix} 2&-4\\4&-6 \end{bmatrix}
    $$

    $$
    \det{\begin{bmatrix} 2-\lambda&-4\\4&-6-\lambda \end{bmatrix}} = 0
    $$

    $$
    \begin{align*}
        f(\lambda) &= \lambda^2 +4\lambda +4 = 0\\
                   &(\lambda +2)(\lambda +2) = 0\\
        \lambda &= -2, -2
    \end{align*}
    $$

    $$
    \begin{align*}
        \lambda_1 &= -2,\\
        A-(-2)I &= \begin{bmatrix} 4&-4\\4&-4 \end{bmatrix} \\
                &= \begin{bmatrix} 4 & -4\\0&0\end{bmatrix} \\
                4x_0-4x_1 &= 0\\
                x_0 &= x_1\\
                \begin{bmatrix}x_0\\x_1\end{bmatrix} &= x_1\begin{bmatrix}1\\1\end{bmatrix}\\
                \therefore v_1 &= \begin{bmatrix}1\\1\end{bmatrix}
    \end{align*}
    $$

    Eigenspace just one dim, but matrix is not symmetric\\
    So it is okay that we do not have 2 eigenvalues nor 2 eigenvectors. (We cant compute D since there is only 1 eigenvector)\\


\end{homeworkProblem}
\pagebreak

\begin{homeworkProblem}
    \begin{itemize}
        \item Compute an eigenvector for the eigenvalue $x = 3$ for the below $(3,3)$-matrix. Note: nobody asks you to compute its characteristic polynomial or to get all of its eigenvalues (Prof did it)
        \item Validate that the found eigenvector $v$ is indeed the correct one, that is, that $Av = 3v$ holds.
    \end{itemize}

    $$
        A = \begin{bmatrix} 1&0&1\\0&1&-1\\2&4&4 \end{bmatrix} 
    $$

    \solution

    $$
    \begin{align*}
        A-\lambda I &= \begin{bmatrix} 1-\lambda&0&1\\0&1-\lambda&-1\\2&4&4-\lambda \end{bmatrix} \\
        f{\lambda} &= - \lambda^3 + +6\lambda^2 - 11\lambda + 6 = 0\\
        f(3) &= 3^3 - 6\cdot3^2 + 11\cdot3 + 6 = 0\\
    \end{align*}
    $$
        When $\lambda = 3&,\\

        $$
        \begin{align*}
            A-3I &= \begin{bmatrix} -2&0&1\\0&-2&-1\\2&4&1 \end{bmatrix} \\
                 &= \begin{bmatrix} -2&0&1\\0&-2&-1\\0&0&0 \end{bmatrix} 
        \end{align*}
        $$

        $1^{st}$ row: $-2x_0 + x_2 = 0 \Rightarrow x_0 = \frac{1}{2}x_2$\\
        $2^{nd}$ row: $-2x_1 - x_2 = 0 \Rightarrow x_1 = -\frac{1}{2}x_2$\\

        $$
        \begin{align*}
            \begin{bmatrix}x_0\\x_1\\x_2\end{bmatrix} &= x_2 \begin{bmatrix}\frac{1}{2}\\-\frac{1}{2}\\1\end{bmatrix}\\
            \therefore v &= \begin{bmatrix}1\\-1\\2\end{bmatrix}
        \end{align*}
        $$

        Verify:
        $$
        \begin{bmatrix}1&0&1\\0&1&-1\\2&4&4 \end{bmatrix}\begin{bmatrix}1\\-1\\2\end{bmatrix} = 3\begin{bmatrix}1\\-1\\2\end{bmatrix}
        $$
        

\end{homeworkProblem}
\pagebreak

\begin{homeworkProblem}
    $$
    A = \begin{bmatrix} 1&1\\0&1 \end{bmatrix}
    $$
    \begin{itemize}
        \item Show that this matrix has only the eigenvalue $1$, twice.
        \item Prove that there cannot exist any matrix P such that $P^{-1}DP = A$. Hint: You know how $D$ in $P^{-1}DP$ must look like
        \item Find an eigenvector
    \end{itemize}
    Bonus knowldge: Shear matrices have an eigenspace of dimensionality $d-1$. In the above case the set of all eigenvectors must be $cv, c \in \mathbb{R}$ for some vector $v$.\\
    \solution

    $$
    A = \begin{bmatrix} 1&1\\0&1 \end{bmatrix}
    $$

    $$
    A - \lambda I = \begin{bmatrix} 1-\lambda&1\\0&1-\lambda \end{bmatrix}
    $$

    $$
    f(\lambda) = (\lambda -1)^2 = 0
    $$

    So only $\lambda = 1$ is a solution. It has 2 eigenvalues equal to 1 (\textit{eigenvalue `1` has algebraic mutiplicity of 2})\\

    Suppose P exists such that $P^{-1}DP = A$, then $D = \begin{bmatrix}1&0\\0&1\end{bmatrix}$\\
    $P^{-1}DP = P^{-1}IP = P^{-1}P = I$\\
    But A is not the identity matrix. So there cannot exist any P as assumed above (Proof by Contradiction)

    $$
    A-I = \begin{bmatrix} o&1\\0&0 \end{bmatrix}
    $$

    $$0\cdot x_0 + 1 \cdot x_1 = 0 \Rightarrow x_1 = 0$$
    $$\begin{bmatrix}x_0\\x_1\end{bmatrix} = \begin{bmatrix}1\\0\end{bmatrix}$$
    $$\therefore \text{ eigenvector } v = \begin{bmatrix}1\\0\end{bmatrix}$$

\end{homeworkProblem}
\pagebreak

\begin{homeworkProblem}
    Show that $$\begin{bmatrix} 2&-4\\\frac{13}{4}&-4 \end{bmatrix}$$
    \begin{itemize}
        \item has no real eigenvalue
        \item Bonus: what are its complex-valued eigenvalues?
    \end{itemize}

    \solution

    $$
    A-\lambda I = \begin{bmatrix} 2-\lambda&-4\\ \frac{13}{4}&-4-\lambda \end{bmatrix}
    $$

    $$f(\lambda) = (\lambda - 2)(\lambda + 4) = \lambda^2 +2\lambda +5 = 0$$
    $$\lambda = \frac{-(2)\pm \sqrt{(2)^2 - 4\cdot 5}}{2} = \frac{-2\pm 2\sqrt{5}}{2} = \frac{-2\pm\sqrt{-1}\sqrt{16}}{2} = \frac{-2\pm i(4)}{2}=-1\pm2i$$

    There are no real eigenvalues.

\end{homeworkProblem}
\pagebreak

\begin{homeworkProblem}
    Bonus Matrix:
    \begin{itemize}
        \item Get its eigenvalues and eigenvectors
    \end{itemize}
    Note: This is a symmetric one, so you can expect 2 eigenvalues and orthogonal eigenspace
    $$
    A = \begin{bmatrix}-2&\sqrt{24}\\\sqrt{24}&8 \end{bmatrix}
    $$

    \solution

    $$
    A = \begin{bmatrix}-2&\sqrt{24}\\\sqrt{24}&8 \end{bmatrix}
    $$

    $$
    A-\lambda I = \begin{bmatrix}-2-\lambda&\sqrt{24}\\\sqrt{24}&8-\lambda \end{bmatrix}
    $$
    
    $$
    f(\lambda) = (\lambda + 2)(\lambda - 8) = \lambda^2 - 6\lambda - 40 = (\lambda - 10)(\lambda + 4) = 0
    $$
    So $\lambda = 10$ or $\lambda = -4$

    \begin{multicols}{2}

    $$
    \begin{align*}
        A - -4I &= \begin{bmatrix}2&\sqrt{24}\\\sqrt{24}&12 \end{bmatrix}\\
                &= \begin{bmatrix}\sqrt{24}&12\\0&0\end{bmatrix}\\
                \sqrt{24}x_0+12x_1 &= 0\\
                x_0 &= -\frac{12}{\sqrt{24}}x_1\\
                \begin{bmatrix}x_0\\x_1\end{bmatrix} &= \begin{bmatrix}-\frac{12}{\sqrt{24}}\\1\end{bmatrix}\\
                \therefore v_1 &= \begin{bmatrix}-12\\\sqrt{24}\end{bmatrix}
    \end{align*}
    $$

    \columnbreak

    $$
    \begin{align*}
        A - 10I &= \begin{bmatrix}-12&\sqrt{24}\\\sqrt{24}&-2 \end{bmatrix}\\
                &= \begin{bmatrix}-12&\sqrt{24}\\0&0\end{bmatrix}\\
                -12x_0+\sqrt{24}x_1 &= 0\\
                x_0 &= \frac{\sqrt{24}}{12}x_1\\
                \begin{bmatrix}x_0\\x_1\end{bmatrix} &= \begin{bmatrix}\frac{\sqrt{24}}{12}\\1\end{bmatrix}\\
                \therefore v_2 &= \begin{bmatrix}\sqrt{24}\\12\end{bmatrix}
    \end{align*}
    $$
    \end{multicols}

\end{homeworkProblem}
\pagebreak

\begin{homeworkProblem}
    \begin{itemize}
        \item Use numpy to get its eigenvalues and eigenvectors
        \item Solve $Ax = (3,17,1/3)$ using numpy
        \item Not in exam:
    \end{itemize}
    Compute the characteristic polynomial for 
    $$
    A = \begin{bmatrix}1&2&4\\2&-2&1\\3&1&3 \end{bmatrix}
    $$

    \solution

    $$
    A-\lambda I = \begin{bmatrix}1-\lambda&2&4\\2&-2-\lambda&1\\3&1&3-\lambda \end{bmatrix}
    $$

    $$
    f(\lambda) = -\lambda^3 + 2\lambda^2 +22\lambda+19
    $$

\end{homeworkProblem}
\pagebreak

\begin{homeworkProblem}
    What is the cosine of the angle between
    $$(6,-6,-4,\sqrt{12}),(6,4,2,\sqrt{25})$$

    \solution

\end{homeworkProblem}
\pagebreak

\begin{homeworkProblem}
    Another 3x3 affine system
    \begin{itemize}
        \item Show the intermediate result when the first column is the one hot vector $\begin{bmatrix}1\\0\\0\end{bmatrix}$ for the first time
        \item Show the intermediate result when the matrix has row echelon form for the first time
        \item Get the solution
    \end{itemize}
    $$
    \begin{align*}
        2x-3y+2z &=-4\\
        7x+4.5y-1z &=16\\
        4x +3y+z &=2
    \end{align*}
    $$

    \solution

\end{homeworkProblem}


\end{document}
