<script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
    tex2jax: {inlineMath: [['$', '$']]},
    "HTML-CSS": {
        fonts: ["Neo-Euler"],
    },
    messageStyle: "none"
  });
</script>

<h1 style="font-family: 'Gulliver', serif;">Assignment 01</h1>

**1.** In our lectures, we mentioned that matrices that can represent Euclidean transformations can form a group. Specifically, in 3D space, the set comprising matrices $M_i$ is actually a group, where $M_i = \begin{bmatrix} R_i & \mathbf{t}_i \\\\ \mathbf{0} & 1 \end{bmatrix}$, $R_i \in \mathbb{R}^{3\times3}$ is an orthonormal matrix, $det(R_i) = 1$, and $\mathbf{t}_i \in \mathbb{R}^3$ is a  vector.

Please prove that the set $M_i$ forms a group.

Hint: You need to prove that $M_i$ satisfies the four properties of a group, i.e., the closure, the associativity, the existence of an identity element, and the existence of an inverse element for each group element.

**Proof**:

(a) Closure:

Let $M_1 = \begin{bmatrix} R_1 & \mathbf{t}_1 \\\\ \mathbf{0} & 1 \end{bmatrix}$ and $M_2 = \begin{bmatrix} R_2 & \mathbf{t}_2 \\\\ \mathbf{0} & 1 \end{bmatrix}$ be two arbitrary elements in the set $M_i$.

$$
M_1 M_2 = \begin{bmatrix} R_1 & \mathbf{t}_1 \\\\ \mathbf{0} & 1 \end{bmatrix} \begin{bmatrix} R_2 & \mathbf{t}_2 \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} R_1 R_2 & R_1 \mathbf{t}_2 + \mathbf{t}_1 \\\\ \mathbf{0} & 1 \end{bmatrix}
$$

Since $R_1$ and $R_2$ are orthonormal matrices with determinant 1, we have:

$$
(R_1 R_2)^T (R_1 R_2) = R_2^T R_1^T R_1 R_2 = R_2^T I R_2 = R_2^T R_2 = I \qquad det(R_1 R_2) = det(R_1) det(R_2) = 1 \cdot 1 = 1
$$

Therefore, $R_1 R_2$ is also an orthonormal matrix with determinant 1. Additionally, $R_1 \mathbf{t}_2 + \mathbf{t}_1$ is a vector in $\mathbb{R}^3$. Thus, $M_1 M_2$ is also in the set $M_i$, satisfying the closure property.

(b) Associativity:

Let $M_1, M_2, M_3$ be three arbitrary elements in the set $M_i$. We need to show that $(M_1 M_2) M_3 = M_1 (M_2 M_3)$.

Calculating the left-hand side:

$$
(M_1 M_2) M_3 = \left( \begin{bmatrix} R_1 & \mathbf{t}_1 \\\\ \mathbf{0} & 1 \end{bmatrix} \begin{bmatrix} R_2 & \mathbf{t}_2 \\\\ \mathbf{0} & 1 \end{bmatrix} \right) \begin{bmatrix} R_3 & \mathbf{t}_3 \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} R_1 R_2 & R_1 \mathbf{t}_2 + \mathbf{t}_1 \\\\ \mathbf{0} & 1 \end{bmatrix} \begin{bmatrix} R_3 & \mathbf{t}_3 \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} (R_1 R_2) R_3 & (R_1 R_2) \mathbf{t}_3 + R_1 \mathbf{t}_2 + \mathbf{t}_1 \\\\ \mathbf{0} & 1 \end{bmatrix}
$$

Calculating the right-hand side:

$$
M_1 (M_2 M_3) = \begin{bmatrix} R_1 & \mathbf{t}_1 \\\\ \mathbf{0} & 1 \end{bmatrix} \left( \begin{bmatrix} R_2 & \mathbf{t}_2 \\\\ \mathbf{0} & 1 \end{bmatrix} \begin{bmatrix} R_3 & \mathbf{t}_3 \\\\ \mathbf{0} & 1 \end{bmatrix} \right) = \begin{bmatrix} R_1 & \mathbf{t}_1 \\\\ \mathbf{0} & 1 \end{bmatrix} \begin{bmatrix} R_2 R_3 & R_2 \mathbf{t}_3 + \mathbf{t}_2 \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} R_1 (R_2 R_3) & R_1 (R_2 \mathbf{t}_3 + \mathbf{t}_2) + \mathbf{t}_1 \\\\ \mathbf{0} & 1 \end{bmatrix}
$$

Since matrix multiplication is associative, we have $(R_1 R_2) R_3 = R_1 (R_2 R_3)$. Also, the vector addition is associative, so $(R_1 R_2) \mathbf{t}_3 + R_1 \mathbf{t}_2 + \mathbf{t}_1 = R_1 (R_2 \mathbf{t}_3 + \mathbf{t}_2) + \mathbf{t}_1$. Therefore, $(M_1 M_2) M_3 = M_1 (M_2 M_3)$, satisfying the associativity property.

(c) Identity Element:

The identity element in the set $M_i$ should satisfy $M I = I M = M$ for any $M \in M_i$. The identity element is given by:

$$
I = \begin{bmatrix} I_3 & \mathbf{0} \\\\ \mathbf{0} & 1 \end{bmatrix} \in M_i
$$

Let $M = \begin{bmatrix} R & \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix}$ be an arbitrary element in the set $M_i$. Then,

$$
M I = \begin{bmatrix} R & \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} \begin{bmatrix} I_3 & \mathbf{0} \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} R I_3 & R \cdot \mathbf{0} + \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} R & \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} = M
$$

$$
I M = \begin{bmatrix} I_3 & \mathbf{0} \\\\ \mathbf{0} & 1 \end{bmatrix} \begin{bmatrix} R & \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} I_3 R & I_3 \mathbf{t} + \mathbf{0} \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} R & \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} = M
$$

Thus, the identity element exists in the set $M_i$.

(d) Inverse Element:

Let $M = \begin{bmatrix} R & \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix}$ be an arbitrary element in the set $M_i$. We need to find an inverse element $M^{-1}$ such that $M M^{-1} = M^{-1} M = I$. The inverse element is given by:

$$
M^{-1} = \begin{bmatrix} R^{-1} & -R^{-1} \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} R^T & -R^T \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} \in M_i
$$

$$
M M^{-1} = \begin{bmatrix} R & \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} \begin{bmatrix} R^T & -R^T \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} R R^T & R (-R^T \mathbf{t}) + \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} I_3 & \mathbf{0} \\\\ \mathbf{0} & 1 \end{bmatrix} = I
$$

$$
M^{-1} M = \begin{bmatrix} R^T & -R^T \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} \begin{bmatrix} R & \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} R^T R & R^T \mathbf{t} - R^T \mathbf{t} \\\\ \mathbf{0} & 1 \end{bmatrix} = \begin{bmatrix} I_3 & \mathbf{0} \\\\ \mathbf{0} & 1 \end{bmatrix} = I
$$

Thus, the inverse element exists in the set $M_i$.

**2.** When deriving the Harris corner detector, we get the following matrix $M$ composed of first-order partial derivatives in a local image patch $w$,

$$
M = \begin{bmatrix} \displaystyle\sum_{(x_i,y_i) \in w} I_x^2 & \displaystyle\sum_{(x_i,y_i) \in w} I_x I_y \\\\ \displaystyle\sum_{(x_i,y_i) \in w} I_x I_y & \displaystyle\sum_{(x_i,y_i) \in w} I_y^2 \end{bmatrix}
$$

(a) Please prove that $M$ is positive semi-definite.

(b) In practice, $M$ is usually positive definite. If $M$ is positive definite, prove that in the Cartesian coordinate system, $x^T M x = 1$ represents an ellipse.

(c) Suppose that $M$ is positive definite and its two eigen-values are $\lambda_1$ and $\lambda_2$ and $\lambda_1 > \lambda_2 > \mathbf{0}$. For the ellipse defined by $x^T M x = 1$, prove that the length of its semi-major axis is $\dfrac{1}{\sqrt{\lambda_2}}$ while the length of its semi-minor
axis is $\dfrac{1}{\sqrt{\lambda_1}}$.

**Proof**:

(a) For any non-zero vector $\mathbf{x} = \begin{bmatrix} x \\\\ y \end{bmatrix}$,

$$
\begin{aligned}
    \mathbf{x}^T M \mathbf{x}
    &= \begin{bmatrix} x & y \end{bmatrix} \begin{bmatrix} \displaystyle\sum_{(x_i,y_i) \in w} I_x^2 & \displaystyle\sum_{(x_i,y_i) \in w} I_x I_y \\\\ \displaystyle\sum_{(x_i,y_i) \in w} I_x I_y & \displaystyle\sum_{(x_i,y_i) \in w} I_y^2 \end{bmatrix} \begin{bmatrix} x \\\\ y \end{bmatrix} \\\\
    &= \begin{bmatrix} x & y \end{bmatrix} \begin{bmatrix} \displaystyle\sum_{(x_i,y_i) \in w} I_x^2 x + \displaystyle\sum_{(x_i,y_i) \in w} I_x I_y y \\\\ \displaystyle\sum_{(x_i,y_i) \in w} I_x I_y x + \displaystyle\sum_{(x_i,y_i) \in w} I_y^2 y \end{bmatrix} \\\\
    &= \displaystyle\sum_{(x_i,y_i) \in w} (I_x x)^2 + 2 \displaystyle\sum_{(x_i,y_i) \in w} I_x I_y x y + \displaystyle\sum_{(x_i,y_i) \in w} (I_y y)^2 \\\\
    &= \displaystyle\sum_{(x_i,y_i) \in w} ((I_x x)^2 + 2 I_x I_y x y + (I_y y)^2) \\\\
    &= \displaystyle\sum_{(x_i,y_i) \in w} (I_x x + I_y y)^2 \geq 0
\end{aligned}
$$

Thus, $M$ is positive semi-definite.

(b) Since $M$ is positive definite, it is symmetric and can be diagonalized. We can decompose $M$ as $M = Q \Lambda Q^T$, where $Q$ is an orthogonal matrix whose columns are the eigenvectors of $M$, and $\Lambda$ is a diagonal matrix with positive eigenvalues $\lambda_1$ and $\lambda_2$ on the diagonal.

Thus, we can rewrite the equation $\mathbf{x}^T M \mathbf{x} = 1$ as:

$$
\mathbf{x}^T M \mathbf{x} = \mathbf{x}^T Q \Lambda Q^T \mathbf{x} = (Q^T \mathbf{x})^T \Lambda (Q^T \mathbf{x}) = \mathbf{y}^T \Lambda \mathbf{y} = \begin{bmatrix} x' & y' \end{bmatrix} \begin{bmatrix} \lambda_1 & 0 \\\\ 0 & \lambda_2 \end{bmatrix} \begin{bmatrix} x' \\\\ y' \end{bmatrix} = \lambda_1 x'^2 + \lambda_2 y'^2 = 1
$$

where $\mathbf{y} = Q^T \mathbf{x} = \begin{bmatrix} x' \\\\ y' \end{bmatrix}$.

This equation represents an ellipse in the $x'y'$-coordinate system, which is a rotated version of the original $xy$-coordinate system. Therefore, in the Cartesian coordinate system, $\mathbf{x}^T M \mathbf{x} = 1$ represents an ellipse.

(c) From the equation of the ellipse in the $x'y'$-coordinate system:

$$
\lambda_1 x'^2 + \lambda_2 y'^2 = \dfrac{x'^2}{\frac{1}{\lambda_1}} + \dfrac{y'^2}{\frac{1}{\lambda_2}} = 1
$$

The lengths of the semi-major and semi-minor axes of the ellipse are given by the square roots of the denominators:

* Semi-major axis length: $a = \dfrac{1}{\sqrt{\lambda_2}}$
* Semi-minor axis length: $b = \dfrac{1}{\sqrt{\lambda_1}}$

Here is the extracted text and formulas from the image:

**3.** In the lecture, we talked about the least square method to solve an over-determined linear system $Ax = b$, $A \in \mathbb{R}^{m \times n}$, $\mathbf{x} \in \mathbb{R}^{n \times 1}$, $m > n$, $rank(A) = n$. The closed form solution is $\mathbf{x} = (A^T A)^{-1} A^T b$. Try to prove that $A^T A$ is non-singular (or in other words, it is invertible).

**Proof**:

Since $A \in \mathbb{R}^{m \times n}$, $A^T A \in \mathbb{R}^{n \times n}$. $(A^T A)^T = A^T (A^T)^T = A^T A$, so $A^T A$ is symmetric.

Since $rank(A) = n$, the equation $A \mathbf{x} = 0$ has only the trivial solution $\mathbf{x} = 0$.

Suppose $A^T A x = 0$, multiply both sides by $\mathbf{x}^T$:

$$
\mathbf{x}^T A^T A \mathbf{x} = (A \mathbf{x})^T (A \mathbf{x}) = \Vert A \mathbf{x} \Vert^2 = 0
$$

This implies that $A \mathbf{x} = 0$. Since the only solution to this equation is $\mathbf{x} = 0$, we conclude that $null(A^T A) = \\{0\\}$. Thus, $A^T A$ is non-singular and invertible.
