# Is there an easy way to tell if a set of quadratic constraints are solvable

I am trying to find a matrix whose null space $$N\in\mathbb{R}^{9 \times n}$$ does not intersect with the column space of the matrix

$$M(R) = \begin{bmatrix} 0 & -r_3 & r_2 \\ r_3 & 0 & -r_1 \\ -r_2 & r_1 & 0 \end{bmatrix} \in\mathbb{R}^{9\times3}, \tag{1}$$

where $$r_1,r_2,r_3\in\mathbb{R}^3$$ are be the columns of any rotation matrix $$R=\begin{bmatrix}r_1 & r_2 & r_3\end{bmatrix}\in SO(3)$$. A rotation matrix has the property that $$r_i^\top\,r_j$$ is equal to zero if $$i \neq j$$ and is equal to one if $$i=j$$.

Instead of finding $$N$$ I am first trying to see if I can tell whether for a given $$N$$ there exists a rotation matrix which does intersect. So I need to find $$u\in\mathbb{R}^n$$, $$v\in\mathbb{R}^3$$ and $$R\in SO(3)$$ such that

$$N\,u = M(R)\,v. \tag{2}$$

When using the properties of $$r_i^\top\,r_j$$ for each column of $$M$$ I am able to formulate the following relations independently of $$R$$

\begin{align} u^\top N^\top \begin{bmatrix} I & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} N\,u &= v^\top \begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} v, \tag{3a} \\ u^\top N^\top \begin{bmatrix} 0 & I & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} N\,u &= v^\top \begin{bmatrix} 0 & -1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} v, \tag{3b} \\ u^\top N^\top \begin{bmatrix} 0 & 0 & I \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} N\,u &= v^\top \begin{bmatrix} 0 & 0 & -1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} v, \tag{3c} \\ u^\top N^\top \begin{bmatrix} 0 & 0 & 0 \\ 0 & I & 0 \\ 0 & 0 & 0 \end{bmatrix} N\,u &= v^\top \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} v, \tag{3d} \\ u^\top N^\top \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & I \\ 0 & 0 & 0 \end{bmatrix} N\,u &= v^\top \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & -1 \\ 0 & 0 & 0 \end{bmatrix} v, \tag{3e} \\ u^\top N^\top \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & I \end{bmatrix} N\,u &= v^\top \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} v, \tag{3f} \end{align}

with $$I$$ the identity matrix $$\in\mathbb{R}^{3 \times 3}$$. It can also be shown that

$$M(R)\,v = \text{vec}\left( \begin{bmatrix} v \times r_1^* & v \times r_2^* & v \times r_3^* \end{bmatrix}^\top \right), \tag{4}$$

with $$r_1^*,r_2^*,r_3^*\in\mathbb{R}^3$$ the column vectors of $$R^\top$$ and $$\text{vec}(X)$$ is the vectorization of $$X$$. So every $$v \times r_i^*$$ should be perpendicular to $$v$$, which can be formulates as

\begin{align} v^\top \left(I \otimes \begin{bmatrix}1 & 0 & 0\end{bmatrix}\right) N\,u &= 0, \tag{5a} \\ v^\top \left(I \otimes \begin{bmatrix}0 & 1 & 0\end{bmatrix}\right) N\,u &= 0, \tag{5b} \\ v^\top \left(I \otimes \begin{bmatrix}0 & 0 & 1\end{bmatrix}\right) N\,u &= 0, \tag{5c} \end{align}

where $$\otimes$$ is the Kronecker product. When using $$x:=\begin{bmatrix}u^\top & v^\top\end{bmatrix}^\top$$ then $$(3)$$ and $$(5)$$ can be written as nine constraints of the form $$x^\top A_i\,x = 0$$. To avoid the trivial solution $$x=0$$ one could also add a tenth constraint $$x^\top x = 1$$.

But here is my question, how can I tell if I can find a $$x$$ that satisfies all ten constraints? Or is there another way of telling if $$(2)$$ has a solution?

• @reuns I indeed used that $N\,u=M\,e$, with $N$ the null space of the given matrix and $e$ one of the columns of an identity matrix. Since $M\,e$ always partially contains a zero vector, so $u$ should lie in the null space of a submatrix of $N$. This then enables me to derive the $A$ and $B$ matrices. So I know that $N\,u=M\,e$ can be solved, however the problem is that $r_1$, $r_2$ and $r_3$ also have to be orthonormal basis vectors. – Kwin van der Veen Apr 17 at 11:41
• No column space in what you wrote. You want to know if some of the column of $M$ is in the kernel of the given matrix $A$. So for each column $u_i = M e_i$ check if $Au_i=0$. – reuns Apr 17 at 11:45
• @reuns But then I would have to check this for every possible rotation matrix. – Kwin van der Veen Apr 17 at 11:50
• Let $R = \{ \scriptstyle{\pmatrix{ 0 & -r_3 & r_2 \\r_3 & 0 & -r_1 \\ -r_2 & r_1 & 0 }}, r_1^2+r_2^2+r_3^3=1\}$ and $A$ a matrix. Is problem your to find $\{ M \in R, \exists e_j, A M e_j = 0\}$ ? If so then it reduces to solve $3$ problems of the same kind as $\{ r_2^2+r_3^2 \le 1, A \scriptstyle{\pmatrix{0 \\ r_3 \\ -r_2}} = 0\}$ which reduces to $\{ x,y, A \scriptstyle{\pmatrix{0 \\ x \\ y}} = 0\}$ ie. computing a basis for the kernel of $3$ submatrices of $A$. – reuns Apr 17 at 12:02
• @reuns The definition of $R$ is not correct, namely $r_1,r_2,r_3\in\mathbb{R}^3$ such that the rotation matrix $R'=\begin{bmatrix}r_1 & r_2 & r_3\end{bmatrix}\in\mathbb{R}^{3\times3}\in SO(3)$. So $R'^\top R' = I$ and $\det R' = 1$. – Kwin van der Veen Apr 17 at 12:10