I have the matrix of stacked constraints
$$\begin{bmatrix} x_1^2 & x_1y_1 & y_1^2 & x_1 & y_1 & 1 \\ x_2^2 & x_2y_2 & y_2^2 & x_2 & y_2 & 1 \\ x_1^2 & x_3y_3 & y_3^2 & x_3 & y_3 & 1 \\ x_4^2 & x_4y_4 & y_4^2 & x_4 & y_4 & 1 \\ x_5^2 & x_5y_5 & y_5^2 & x_5 & y_5 & 1 \end{bmatrix} \mathbf{c} = \mathbf{0},$$
where $\mathbf{c} = (a, b, c, d, e, f)^T$ is a conic.
So $\mathbf{c}$ is the null vector of this $5 \times 6$ matrix. Apparently, this shows that $\mathbf{c}$ is determined uniquely (up to scale) by five points in general position. What is the concept from linear algebra that tells us that this shows that $\mathbf{c}$ is determined uniquely? And what is meant by "up to scale"?
Thank you.
Best Answer
a linear algebra (+ Kronecker products) proof of the rank of your interpolation matrix
$\begin{bmatrix} x_1^2 & x_1y_1 & y_1^2 & x_1 & y_1 & 1 \\ x_2^2 & x_2y_2 & y_2^2 & x_2 & y_2 & 1 \\ x_3^2 & x_3y_3 & y_3^2 & x_3 & y_3 & 1 \\ x_4^2 & x_4y_4 & y_4^2 & x_4 & y_4 & 1 \\ x_5^2 & x_5y_5 & y_5^2 & x_5 & y_5 & 1 \end{bmatrix} \mathbf{c} = \mathbf{0}$
and you want to prove that the nullspace has dimension 1 -- so up to rescaling, there is one and only one nonzero vector in the nullspace of that matrix. By rank-nullity this is equivalent to proving the above matrix has rank 5.
Permuting columns doesn't change rank. Also appending columns that are copies of existing columns doesn't change rank,so it becomes convenient to consider instead the rank of
$\begin{bmatrix} x_1^2 & x_1y_1 & x_1 & x_1 y_1& y_1^2 & y_1 & x_1 & y_1 & 1 \\\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\x_5^2 & x_5y_5 & x_5 & x_5 y_5& y_5^2 & y_5 & x_5 & y_5 & 1 \end{bmatrix} = \begin{bmatrix} \mathbf x_1^T\otimes \mathbf x_1^T \\ \vdots \\ \mathbf x_5^T\otimes \mathbf x_5^T\\ \end{bmatrix}$
where
$\mathbf x_k := \begin{bmatrix} x_k \\ y_k \\ 1\end{bmatrix}$
and $\otimes$ denotes Kronecker Product
again it must be the case that
$\text{rank}\left(\begin{bmatrix} x_1^2 & x_1y_1 & y_1^2 & x_1 & y_1 & 1 \\ x_2^2 & x_2y_2 & y_2^2 & x_2 & y_2 & 1 \\ x_3^2 & x_3y_3 & y_3^2 & x_3 & y_3 & 1 \\ x_4^2 & x_4y_4 & y_4^2 & x_4 & y_4 & 1 \\ x_5^2 & x_5y_5 & y_5^2 & x_5 & y_5 & 1 \end{bmatrix}\right) = \text{rank}\left(\begin{bmatrix} \mathbf x_1^T\otimes \mathbf x_1^T \\ \vdots \\ \mathbf x_5^T\otimes \mathbf x_5^T\\ \end{bmatrix}\right)$
so we want to prove that
$\text{rank}\left(\begin{bmatrix} \mathbf x_1^T\otimes \mathbf x_1^T \\ \vdots \\ \mathbf x_5^T\otimes \mathbf x_5^T\\ \end{bmatrix}\right) = 5$
or using the equivalence of row and column rank, it's equivalent to to prove that
$\Big\{\mathbf x_1\otimes \mathbf x_1, \mathbf x_2\otimes \mathbf x_2, \mathbf x_3\otimes \mathbf x_3. \mathbf x_4\otimes \mathbf x_4, \mathbf x_5\otimes \mathbf x_5\Big\}$
is a linearly independent set (of 5 vectors)
now using the fact that (no subset of 3) of the 5 points selected for interpolation are colinear we choose 3 (WLOG assume the first 3) and form a basis to write the others in terms of. Since the original points are not colinear this implies many things, including
(i) $\det\big(A\big) \neq 0$, (ii) $\mathbf z_4$ and $\mathbf z_5$ have no components equal to zero and (iii) $\mathbf z_4 \not\propto \mathbf z_5$
So
$A :=\bigg[\begin{array}{c|c|c} \mathbf x_1 & \mathbf x_2 & \mathbf x_3 \end{array}\bigg]$
and
$\mathbf x_1 = A\mathbf e_1$
$\mathbf x_2 = A\mathbf e_2$
$\mathbf x_3 = A\mathbf e_3$
$\mathbf x_4 = A\mathbf z_4$
$\mathbf x_5 = A\mathbf z_5$
where $\mathbf e_k$ is the kth standard basis vector in $\mathbb R^3$.
applying the Kronecker product
$\mathbf x_1\otimes \mathbf x_1 = \big(A\mathbf e_1\big)\otimes \big(A\mathbf e_1\big) = \big(A\otimes A\big)\big(\mathbf e_1 \otimes \mathbf e_1\big)$
$\mathbf x_2\otimes \mathbf x_2 =\big(A\otimes A\big)\big(\mathbf e_2 \otimes \mathbf e_2\big)$
$\mathbf x_3\otimes \mathbf x_3 = \big(A\otimes A\big)\big(\mathbf e_3 \otimes \mathbf e_3\big)$
$\mathbf x_4\otimes \mathbf x_4 = \big(A\otimes A\big)\big(\mathbf z_4 \otimes \mathbf z_4\big)$
$\mathbf x_5\otimes \mathbf x_5 = \big(A\otimes A\big)\big(\mathbf z_5 \otimes \mathbf z_5\big)$
so our linearly independent set at least includes
$\Big\{\mathbf e_1\otimes \mathbf e_1,\mathbf e_2\otimes \mathbf e_2, \mathbf e_3\otimes \mathbf e_3\Big\}$
i.e. 3 vectors that are all zero except they have a single one in the 1st, 5th, and 9th components respectively (i.e. they are $\mathbf e_1, \mathbf e_5, \mathbf e_9 \in \mathbb R^9$)
Now $\mathbf z_4$ has every component non-zero so it can't possibly be a linear combination of those three vectors. Thus we have a linearly independent set including at least
$\Big\{\mathbf e_1\otimes \mathbf e_1,\mathbf e_2\otimes \mathbf e_2, \mathbf e_3\otimes \mathbf e_3, \mathbf z_4 \otimes \mathbf z_4\Big\}$
it remains to prove $\mathbf z_5 \otimes \mathbf z_5$ cannot be written as a linear combination of vectors in that set. In particular we'll prove that
$\alpha \mathbf z_4 \otimes \mathbf z_4 + \mathbf z_5 \otimes \mathbf z_5\neq \sum_{k=1}^3 \gamma_k\mathbf e_k\otimes \mathbf e_k$
the problem is easy to finish by using a simple isomorphism. I.e. consider
$\text{vec}\big(\mathbf z_j \mathbf z_j^T \big) =\big(\mathbf z_j \otimes \mathbf z_j \big)$
where the vec operator just takes a matrix and converts it into a 'big vector' by stacking one column on top of the other.
so to finish, it's sufficient to prove that it's impossible to have
$\alpha \mathbf z_4 \mathbf z_4^T + \mathbf z_5 \mathbf z_5^T=D$
for some diagonal matrix $D \in \mathbb R^\text{3 x 3}$
note: if $D$ exists, then $3 =\text{rank}\big(D\big)$. If this wasn't the case then there is (at least one) diagonal component $d_{k,k} = 0$, which implies
$\alpha \mathbf z_4 \mathbf z_4^T\mathbf e_k + \mathbf z_5 \mathbf z_5^T\mathbf e_k = \alpha z_4^{(k)}\mathbf z_4 +z_5^{(k)} \mathbf z_5 =\mathbf 0 = D\mathbf e_k$ or
$\mathbf z_4 \propto \mathbf z_5 $
since all components of $\mathbf z_4$ and $\mathbf z_5$ are non-zero. But the above is impossible since no points are colinear-- i.e. recall (ii) and (iii). Note: the trivial case of setting $\alpha:=0$ is also covered because that would imply $\mathbf z_5=\mathbf 0 $ but that is impossible as well -- (ii) or (iii) will do it.
Thus if $D$ exists it must be the case that
$3 =\text{rank}\big(D\big) = \text{rank}\big(\alpha \mathbf z_4 \mathbf z_4^T +\mathbf z_5 \mathbf z_5^T\big) \leq 2$
where the right inequality follows because the sum of 2 rank one matrices is at most rank 2. Thus
$\alpha \mathbf z_4 \mathbf z_4^T + \mathbf z_5 \mathbf z_5^T \neq D$
which proves
$\Big\{\mathbf e_1\otimes \mathbf e_1,\mathbf e_2\otimes \mathbf e_2, \mathbf e_3\otimes \mathbf e_3, \mathbf z_4 \otimes \mathbf z_4, \mathbf z_5 \otimes \mathbf z_5 \Big\}$
is a linearly independent set and by the invertibility of $\big(A\otimes A\big)$ we know
$\Big\{\mathbf x_1\otimes \mathbf x_1, \mathbf x_2\otimes \mathbf x_2, \mathbf x_3\otimes \mathbf x_3. \mathbf x_4\otimes \mathbf x_4, \mathbf x_5\otimes \mathbf x_5\Big\}$
is a linearly independent set as well, which proves
$5 =\text{rank}\left(\begin{bmatrix} \mathbf x_1^T\otimes \mathbf x_1^T \\ \vdots \\ \mathbf x_5^T\otimes \mathbf x_5^T\\ \end{bmatrix}\right)= \text{rank}\left(\begin{bmatrix} x_1^2 & x_1y_1 & y_1^2 & x_1 & y_1 & 1 \\ x_2^2 & x_2y_2 & y_2^2 & x_2 & y_2 & 1 \\ x_3^2 & x_3y_3 & y_3^2 & x_3 & y_3 & 1 \\ x_4^2 & x_4y_4 & y_4^2 & x_4 & y_4 & 1 \\ x_5^2 & x_5y_5 & y_5^2 & x_5 & y_5 & 1 \end{bmatrix} \right)$
and completes the proof
post script
a convenient property of the Kronecker product is
$\text{vec}\big(\mathbf {XYZ}\big) = \big(\mathbf Z^T \otimes \mathbf X\big)\text{vec}\big(\mathbf {Y}\big)$
In context of the interpolation problem here, the problem is to collect, with (non-colinear) $\mathbf x_k$, the values of
$\mathbf x_k^T C \mathbf x_k = 0$
for $k\in\{1,2,3,4,5\}$, where $C := \begin{bmatrix} a & b/2 & d/2 \\ b/2 & c & e/2 \\ d/2 & e/2 & f \end{bmatrix}$
so using the Kronecker product we can organize the quadratic form into a convenient a system of equations
$0 = \mathbf x_k^T C \mathbf x_k \longrightarrow 0 = \text{vec}\big(0\big) = \text{vec}\big(\mathbf x_k^T C \mathbf x_k\big) =\big(\mathbf x_k^T \otimes \mathbf x_k^T\big) \text{vec}\big( C\big)$
for $k\in\{1,2,3,4,5\}$. And we can collect this system of equations as
$\begin{bmatrix} \mathbf x_1^T\otimes \mathbf x_1^T \\ \vdots \\ \mathbf x_5^T\otimes \mathbf x_5^T\\ \end{bmatrix}\text{vec}\big( C\big) = \mathbf 0$
after deleting redundant columns (and associated components in $\text{vec}\big( C\big)$), we recover the original problem of
$\begin{bmatrix} x_1^2 & x_1y_1 & y_1^2 & x_1 & y_1 & 1 \\ x_2^2 & x_2y_2 & y_2^2 & x_2 & y_2 & 1 \\ x_3^2 & x_3y_3 & y_3^2 & x_3 & y_3 & 1 \\ x_4^2 & x_4y_4 & y_4^2 & x_4 & y_4 & 1 \\ x_5^2 & x_5y_5 & y_5^2 & x_5 & y_5 & 1 \end{bmatrix} \mathbf{c} = \mathbf{0}$