1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ A key item underlying this: (dropping in from wikipedia link on 5 points...) "given any five points in the plane in general linear position, meaning no three collinear" i.e. ---when you look at $ X: = \begin{bmatrix} \mathbf x_1^T \\ \mathbf x_2^T\\ \vdots \\ \mathbf x_5^T\\ \end{bmatrix}= \begin{bmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1\\ \vdots & \vdots & \vdots \\ x_5 & y_5 & 1\\ \end{bmatrix}$ and delete any 2 rows, you are left with a matrix with non-zero determinant. With this knowledge, one could get to the result using linear algebra (inclusive of Kronecker products). $\endgroup$ – user8675309 Feb 12 '20 at 7:14
  • $\begingroup$ @user8675309 But doesn't that mean that we need to delete two rows in order to get to linear independence? So how does that answer the question of why the matrix of 5 rows is linearly independent? Doesn't it contradict it? (I'm not experienced in geometry, so please excuse my bad understandings.) $\endgroup$ – Dom Fomello Feb 12 '20 at 7:19
  • $\begingroup$ I meant the deletion in terms of arbitrary rows of my $X$ matrix -- not your original matrix per se -- the statement gives some rather strong ideas about row rank. I'm debating typing something up -- the proof I have in mind is heavy on kronecker products and coordinates... my guess is it won't make much sense since your main question was on rank-nullity, but it would be a more accessible approach than wikipedia. $\endgroup$ – user8675309 Feb 12 '20 at 8:18
  • $\begingroup$ @user8675309 It's probably best to not waste your time (I don't want to waste your time), since I probably won't understand it. But what you originally said kind of makes sense to me, since a non-zero determinant indicates that the rows are linearly independent, right? But my point is that, if we need to delete 2 rows in order for the matrix to have a non-zero determinant, then, since your matrix has 5 rows, as does the one in my post, then how can we claim that the matrix with 5 rows (my matrix) is linearly independent? These statements seem to be contradictory? $\endgroup$ – Dom Fomello Feb 12 '20 at 8:25
  • $\begingroup$ I ended up typing up the proof and submitting it. It'll go over your head but is the simplest proof of this result that is on this site so I dropped it in as it may help some others. $\endgroup$ – user8675309 Feb 13 '20 at 8:26
0
$\begingroup$

It means that your matrix has rank 5, so its null space has dimension $6-5=1$. This means that you have exactly one nonzero solution $c$ with norm/magnitude/length 1 and whose first nonzero entry is positive. Any other solution is a multiple of that $c$, or in other words a scaling of $c$.

$\endgroup$
12
  • $\begingroup$ Thank you. So I'm assuming that you used the Rank-nullity theorem en.wikipedia.org/wiki/Rank–nullity_theorem ? So you found that $nullity = dim - rank = 6 - 5$? Can you please explain why $dim = 6$ and $rank = 5$? $\endgroup$ – Dom Fomello Feb 11 '20 at 6:51
  • $\begingroup$ The null space is a subspace of your input space and the latter has dimension 6. Regarding the rank note that the columns are six vectors in a five dimensional space, hence they are linearly dependent. Thus the rank of this matrix has to be $\leq5$. Tbh I concluded that it has rank 5 from your remark on uniqueness of $c$, which is of course reverse engineered. If you want to see a full proof, I would like to know more about the $x_i, y_i$ things. In other words: What are your five points in general position? $\endgroup$ – PrudiiArca Feb 11 '20 at 7:00
  • $\begingroup$ Thanks. What you've said makes sense to me. So the equation of a conic in homogeneous coordinates is $$ax_1^2 + bx_1x_2 + cx_2^2 + dx_1x_3 + ex_2x_3 + fx_3^2 = 0,$$ or $\mathbf{x}^T C \mathbf{x} = 0$ in matrix form, where the conic coefficient matrix $C$ is given by $$C = \begin{bmatrix} a & b/2 & d/2 \\ b/2 & c & e/2 \\ d/2 & e/2 & f \end{bmatrix}.$$ So each point $\mathbf{x}_i$ places one constraint on the conic coefficients, since if the conic passes through $(x_i, y_i)$, then $ax_i^2 + bx_iy_i + cy_i^2 + dx_i + ey_i + f = 0$. Is there enough information here for us to find the rank? $\endgroup$ – Dom Fomello Feb 11 '20 at 7:23
  • $\begingroup$ @DomFomello I am sorry, but I seem to be too stupid to solve this. I don’t quite get how one comes from general position of the points $(x_i,y_i)$, which is a condition on triples of points, to linear independence of the rows (or five of the columns), which is a condition on 5 points... $\endgroup$ – PrudiiArca Feb 11 '20 at 8:12
  • $\begingroup$ That's ok! Thank you for the help. :) The equation of a conic in inhomogeneous coordinates is $$ax^2 + bxy + cy^2 + dx + ey + f = 0$$ So if we define the mappings $x \mapsto x_i$, $y \mapsto y_i$, we get $$ax_i^2 + bx_iy_i + cy_i^2 + dx_i + ey_i + f = 0.$$ If we assume that the points $(x_i, y_i)$ that the conic passes through are unique, then the rows would indeed be linearly independent, right? I think that might be the under assumption here -- that the points $(x_i, y_i)$ that the conic passes through are unique? $\endgroup$ – Dom Fomello Feb 11 '20 at 9:39
2
$\begingroup$

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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.