# Introduction to Projective Geometry Solutions 5.8

## The Determination of a Collineation

A 12 minute read, posted on 12 Sep 2019

Tags computer vision, projective geometry, problem solution

Please read this introduction first before looking through the solutions. Here’s a quick index to all the problems in this section.

#### 1. Prove Theorem 4 by showing that the determination of the required collineation is equivalent to solving a system of 12 homogeneous linear equations in 13 variables when the rank of the matrix of the coefficients is 12.

Let the matrix of the collineation be $$\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}$$

Let’s represent the 4 given points by $P:(p_1, p_2, p_3)$, $Q:(q_1, q_2, q_3)$, $R:(r_1, r_2, r_3)$, $S:(s_1, s_2, s_3)$ and their images by $P’:(p’_1, p’_2, p’_3)$, $Q’:(q’_1, q’_2, q’_3)$, $R’:(r’_1, r’_2, r’_3)$, $S’:(s’_1, s’_2, s’_3)$.

As these are in homogeneous coordinates, the coordinates obtained by multiplying the matrix of the collineation by the given point can be any scalar multiple of the image point.

Hence, taking $k_1, k_2, k_3, k_4$ to be the unknown scaling factors corresponding to each image point, the following relationships hold between the points, their images and the elements of the matrix of the collineaion.

$$k_1p’_1 = a_{11}p_1 + a_{12}p_2 + a_{13}p_3$$ $$k_1p’_2 = a_{21}p_1 + a_{22}p_2 + a_{23}p_3$$ $$k_1p’_3 = a_{31}p_1 + a_{32}p_2 + a_{33}p_3$$

$$k_2q’_1 = a_{11}q_1 + a_{12}q_2 + a_{13}q_3$$ $$k_2q’_2 = a_{21}q_1 + a_{22}q_2 + a_{23}q_3$$ $$k_2q’_3 = a_{31}q_1 + a_{32}q_2 + a_{33}q_3$$

$$k_3r’_1 = a_{11}r_1 + a_{12}r_2 + a_{13}r_3$$ $$k_3r’_2 = a_{21}r_1 + a_{22}r_2 + a_{23}r_3$$ $$k_3r’_3 = a_{31}r_1 + a_{32}r_2 + a_{33}r_3$$

$$k_4s’_1 = a_{11}s_1 + a_{12}s_2 + a_{13}s_3$$ $$k_4s’_2 = a_{21}s_1 + a_{22}s_2 + a_{23}s_3$$ $$k_4s’_3 = a_{31}s_1 + a_{32}s_2 + a_{33}s_3$$

These is a system of 12 homogeneous linear equations in 13 variables. The matrix for this system will be $$\begin{pmatrix} p_1 & p_2 & p_3 & 0 & 0 & 0 & 0 & 0 & 0 & -p’_1 & 0 & 0 & 0 \\ 0 & 0 & 0 & p_1 & p_2 & p_3 & 0 & 0 & 0 & -p’_2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & p_1 & p_2 & p_3 & -p’_3 & 0 & 0 & 0 \\ q_1 & q_2 & q_3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -q’_1 & 0 & 0 \\ 0 & 0 & 0 & q_1 & q_2 & q_3 & 0 & 0 & 0 & 0 & -q’_2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & q_1 & q_2 & q_3 & 0 & -q’_3 & 0 & 0 \\ r_1 & r_2 & r_3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -r’_1 & 0 \\ 0 & 0 & 0 & r_1 & r_2 & r_3 & 0 & 0 & 0 & 0 & 0 & -r’_2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & r_1 & r_2 & r_3 & 0 & 0 & -r’_3 & 0 \\ s_1 & s_2 & s_3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -s’_1 \\ 0 & 0 & 0 & s_1 & s_2 & s_3 & 0 & 0 & 0 & 0 & 0 & 0 & -s’_2 \\ 0 & 0 & 0 & 0 & 0 & 0 & s_1 & s_2 & s_3 & 0 & 0 & 0 & -s’_3 \end{pmatrix}\begin{pmatrix} a_{11} \\ a_{12} \\ a_{13} \\ a_{21} \\ a_{22} \\ a_{23} \\ a_{31} \\ a_{32} \\ a_{33} \\ k_{1} \\ k_{2} \\ k_{3} \\ k_{4} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}$$

When the rank of the giant matrix above is 12 (due to no three points being collinear), the dimension of the column space will be 12 and as the number of columns is 13, the dimension of its nullspace1 will be 13 - 12 = 1. As the solution we’re looking for lies in the nullspace and as the nullspace has the dimension of exactly one, it will exist and be unique (within an arbitrary scaling factor). This is exactly what Theorem 4 asserts.

#### 2. Find the transformations which effects each of the following mappings:

(a) $(0, 0, 1) \rightarrow (1, -1, 2)$
$(1, -1, 2) \rightarrow (3, 0, 5)$
$(1, 1, 1) \rightarrow (0, 3, 1)$
$(1, 0, 0) \rightarrow (1, -1, 0)$

(b) $(1, 0, 0) \rightarrow (0, 1, 1)$
$(1, -1, 0) \rightarrow (1, -1, 0)$
$(2, 0, 1) \rightarrow (1, 0, 2)$
$(1, -1, 1) \rightarrow (0, 1, 0)$

(c) $(1, 0, 0) \rightarrow (1, 1, 1)$
$(0, 1, 0) \rightarrow (1, 0, 1)$
$(-1, 1, 1) \rightarrow (0, 0, 1)$
$(1, 1, 1) \rightarrow (2, 2, 1)$

(d) $(0, 0, 1) \rightarrow (0, 1, 3)$
$(1, 1, 0) \rightarrow (3, 0, 1)$
$(0, 3, 1) \rightarrow (3, 1, 0)$
$(1, 1, 1) \rightarrow (-3, 1, 2)$

Finding the nullspace of a matrix is super easy using maxima/scipy. Using the technique we derived in the solution to #1, the answers are

(a) $\begin{pmatrix} -3 & 7 & -4 \\ 3 & 11 & 4 \\ 0 & 14 & -8 \end{pmatrix}$

(b) $\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 2 \\ 1 & 1 & 0 \end{pmatrix}$

(c) The transformation for this mapping is not unique as $(1, 0, 0)$, $(-1, 1, 1)$ and $(1, 1, 1)$ are collinear.

The solution space is spanned by the two matrices $$A_1 = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$$ $$A_2 = \begin{pmatrix} 0 & -1 & 1 \\ 0 & 0 & 0 \\ 0 & -1 & 1 \end{pmatrix}$$

Any nonsingular linear combination of these two matrices can serve as the matrix of transformation for this mapping. For example $$A_1 + A_2 = \begin{pmatrix} 1 & -1 & 2 \\ 1 & 0 & 1 \\ 1 & -1 & 1 \end{pmatrix}$$ will result in the mapping provided.

(d) The transformation for this mapping is not unique as $(0, 0, 1)$, $(1, 1, 0)$ and $(1, 1, 1)$ are collinear. The solution space is spanned by the two matrices $$A_1 = \begin{pmatrix} 0 & -27 & 0 \\ 12 & -12 & 9 \\ 0 & -9 & 27 \end{pmatrix}$$ $$A_2 = \begin{pmatrix} 3 & -3 & 0 \\ 1 & -1 & 0 \\ 0 & 0 & 0 \end{pmatrix}$$ Any nonsingular linear combination of these two matrices can serve as the matrix of transformation for this mapping.

#### 3. Show that there is more than one transformation $T$ which will accomplish the following mappings, find the most general form of $T$, and explain why $T$ is not unique:

(a) $(2, 0, 1) \rightarrow (1, 1, 0)$
$(2, 2, 3) \rightarrow (0, 0, 1)$
$(1, 1, 1) \rightarrow (1, 0, 0)$
$(0, 1, 1) \rightarrow (2, 2, 1)$

(b) $(1, 0, 0) \rightarrow (1, 0, 0)$
$(1, 1, 0) \rightarrow (1, 0, -1)$
$(3, 0, -1) \rightarrow (1, -1, 1)$
$(-1, 2, 1) \rightarrow (0, 1, -2)$

(a) As the three points $(2, 0, 1), (2, 2, 3), (0, 1, 1)$ and their corresponding images are collinear multiple transformations will be able to achieve this mapping.

Using the technique of finding the nullspace of a $12 \times 13$ matrix as in #1, we find that the solution space is spanned by the linear combination of the following two matrices.

$$A_1 = \begin{pmatrix} 2 & -2 & 0 \\ 2 & -2 & 0 \\ 1 & 1 & -2 \end{pmatrix}$$

$$A_2 = \begin{pmatrix} 0 & -6 & 4 \\ 2 & -2 & 0 \\ 1 & 1 & -2 \end{pmatrix}$$

Expressing the general linear combination as $pA_1 + qA_2$, we get $$\begin{pmatrix} 2p & -2p - 6q & 4q \\ 2p + 2q & -2p - 2q & 0 \\ p + q & p + q & -2p -2q \end{pmatrix}$$

To get the answer in the book, substitute $p + q = b$, $p = a$ and $q = b - a$. $$\begin{pmatrix} 2a & 4a - 6b & 4b - 4a \\ 2b & -2b & 0 \\ b & b & -2b \end{pmatrix}$$

(b) As the three points $(1, 1, 0), (3, 0, -1), (1, -1, 1)$ and their corresponding images are collinear multiple transformations will be able to achieve this mapping.

Using the technique of finding the nullspace of a $12 \times 13$ matrix as in #1, we find that the solution space is spanned by the linear combination of the following two matrices.

$$A_1 = \begin{pmatrix} -1 & 1 & -3 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}$$

$$A_2 = \begin{pmatrix} 0 & -1 & 2 \\ 0 & 0 & -2 \\ 0 & 1 & 2 \end{pmatrix}$$

Expressing the general linear combination as $pA_1 + qA_2$, we get $$\begin{pmatrix} -p & p - q & -3p + 2q \\ 0 & 0 & -2q \\ 0 & q & 2q \end{pmatrix}$$

To get the answer in the book, substitute $p = -2a$, $q = b$.

#### 4. Verify that there is no collineation which will accomplish either of the following mappings, and explain why:

(a) $(1, 1, -1) \rightarrow (2, 1, 1)$
$(3, 0, -1) \rightarrow (0, 0, 1)$
$(1, -1, 0) \rightarrow (1, 1, 0)$
$(1, -2, 1) \rightarrow (1, 1, 1)$

(b) $(3, 2, 0) \rightarrow (1, -1, 0)$
$(2, 2, 1) \rightarrow (1, 1, 2)$
$(1, 1, 1) \rightarrow (1, 0, 1)$
$(4, 2, -1) \rightarrow (1, 1, 0)$

These mappings can’t be achieved by collineations because a collineation preserves collinearity, but the images $(2, 1, 1), (0, 0, 1), (1, 1, 1)$ of the three collinear points $(1, 1, -1), (3, 0, -1), (1, -2, 1)$ in (a) and the images $(1, -1, 0), (1, 1, 2), (1, 1, 0)$ of the three collinear points $(3, 2, 0), (2, 2, 1), (4, 2, -1)$ in (b) are not collinear.

To verify this assertion, let’s use the technique from #1. The matrices of transformation will be

(a) $\begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \\ 0 & 0 & 0 \end{pmatrix}$

(b) $\begin{pmatrix} 2 & -3 & 2 \\ 0 & 0 & 0 \\ 2 & -3 & 2 \end{pmatrix}$

Both these are singular matrices and hence not collineations.

#### 5. (a) Let $T$ be the collineation which leaves the points $(1, 0, 0)$, $(0, 1, 0)$, $(0, 0, 1)$ invariant and maps the point $P:(y_1, y_2, y_3)$ onto the point $(1, 1, 1)$. Determine the possible types for $T$, and find the locus of $P$ corresponding to each type.(b) Work part (a) if $T$ effects the mapping of $(1, 0, 0) \rightarrow (0, 1, 1)$, $(0, 1, 0) \rightarrow (1, 0, 1)$, $(0, 0, 1) \rightarrow (1, 1, 0)$, $(y_1, y_2, y_3) \rightarrow (1, 1, 1)$

(a) As three non-collinear points are invariant, this can not be a collineation of types II, IV or V. Using the technique in #1, the matrix for this transformation looks like $$\begin{pmatrix} y_2y_3 & 0 & 0 \\ 0 & y_1y_3 & 0 \\ 0 & 0 & y_1y_2 \end{pmatrix}$$ It is clear that if $y_1 \ne y_2 \ne y_3$, this is the canonical matrix for a collineation of type I. If $y_i = y_j \ne y_k$ for any one $k$, then the matrix becomes the canonical matrix of a collineation of type III. Finally, if $(y_1, y_2, y_3)$ is the point $(1, 1, 1)$, we have 4 invariant points with no three of them being collinear, so by Theorem 1 the transformation that achieves this mapping is a collineation of type VI or the identity transformation.

The locus of $P$ in a collineation of type VI is the point $P$ itself. Under a collineation of type III the locus is one of the lines $y_i = y_j$. Under a collineation of type I the locus of $P$ is any point on $\Pi_2$.

(b) Using the technique in #1, the matrix for this transformation looks like $$\begin{pmatrix} 0 & y_1y_3 & y_1y_2 \\ y_2y_3 & 0 & y_1y_2 \\ y_2y_3 & y_1y_3 & 0 \end{pmatrix}$$

The characteristic polynomial of this matrix is $$2y_1^2y_2^2y_3^2 + ky_1y_2y_3(y_1 + y_2 + y_3) - k^3 = 0$$

As this polynomial does not have a $k^2$ term, it can not be the expansion of a cubic polynomial of the form $(k - a)^3$ and hence can’t have a single repeated root. This means it can’t be a collineation of types IV, V or VI.

For it to have one repeated and one simple root, it must be of the form $$(k - a)*(k - b)^2$$

Expanding this we get $$k^3 - k^2(2b + a) + (2ab + b^2)k - ab^2$$

For this to match the characteristic polynomial, the coefficient of the k^2 term must be 0. So we get $$2b = -a$$

Hence the cubic equation can be rewritten as $$k^3 - 3b^2k + 2b^3$$

Matching the coefficients of this cubic equation with the characteristic polynomial, we get

$$-3b^2 = y_1y_2y_3(y_1 + y_2 + y_3) \implies b^2 = -\frac{1}{3}y_1y_2y_3(y_1 + y_2 + y_3)$$ $$2b^3 = 2y_1^2y_2^2y_3^2 \implies b^3 = y_1^2y_2^2y_3^2$$

Raising the first equation to the power of 3 and the second one to the power of 2 we get $$-\frac{1}{27}y_1^3y_2^3y_3^3(y_1 + y_2 + y_3)^3 = y_1^4y_2^4y_3^4$$ $$\implies (y_1 + y_2 + y_3)^3 = 27y_1y_2y_3$$

Hence for the transformation to have a repeated root and a simple root, the locus of $P$ must be $(y_1 + y_2 + y_3)^3 = 27y_1y_2y_3$.

For this to be a collineation of type III, the lines between the points and their images must intersect at the invariant center. In this case it is $(1, 1, 1)$. Hence this will be a collineation of type III if $P$ is $(1, 1, 1)$. In all other cases, any point having the locus $(y_1 + y_2 + y_3)^3 = 27y_1y_2y_3$ will lead to a collineation of type II.

If $P$ is any point not on the curve $(y_1 + y_2 + y_3)^3 = 27y_1y_2y_3$ then the collineation will be of the most general type, type I.