What is the image of $x^{\rm T}Qx\le 1$ under a linear map $x \mapsto Cx$?

Question

Let $Q$ be a real symmetric positive semidefinite $n \times n$ matrix. Consider a set

$$ \Big\{ x \in \mathbb{R}^n \;\Big| \; x^{\rm T}Qx\le 1\Big\}, $$

which can be loosely described as an "elliptic cylinder". (It would be an ellipsoid if $Q$ was positive definite).

Question. What is the image of this set under a linear map $y = Cx$? One can assume that $C$ has full row rank, but no more than that.

I think that it will be $$ \Big\{ y \in \mathbb{R}^m \;\Big| \; y^{\rm T}Ry\le 1\Big\}, $$

where $R$ is some positive semidefinite matrix. But that is not enough: I actually want to find an explicit formula for $R$ (in terms of $Q$ and $C$) $-$ as elementary as it can be.

Answer 1

By changing the orthonormal bases in $\mathbb R^n$ and $\mathbb R^m$, we may assume that $C=\pmatrix{D&0}$ for some nonsingular matrix $D$. Let $$ Q=\pmatrix{X&Y^T\\ Y&Z}, \ M=\pmatrix{I_m&0\\ -Z^+Y&I_{n-m}} \ \text{ and } \ x=\pmatrix{u\\ v}.\tag{1} $$ As $Q$ is positive semidefinite, the range of $Y$ must lie inside the range of $Z$, i.e. $Y=ZW$ for some matrix $W$. It follows that $Y-ZZ^+Y=(Z-ZZ^+Z)W=0$. Hence $$ M^TQM=\pmatrix{X-Y^TZ^+Y&0\\ 0&Z} \ \text{ and } \ M^{-1}x=\pmatrix{u\\ v+Z^+Yu}. $$ Since $x^TQx=(M^{-1}x)^T(M^TQM)(M^{-1}x)$, we obtain $$ x^TQx=u^T(X-Y^TZ^+Y)u+(v+Z^+Yu)^TZ(v+Z^+Yu).\tag{2} $$ $M^TQM$ must be positive semidefinite because it is congruent to $Q$. Thus $X-Y^TZ^+Y$ and $Z$ are also PSD. Now define $$ R:=(D^{-1})^T(X-Y^TZ^+Y)D^{-1}\ \text{ and }\ y:=Cx=Du.\tag{3} $$ If $y=Cx$ for some $x$ with $x^TQx\le1$, $(3)$ shows that $u=D^{-1}y$ is uniquely determined by $y$ and $(2)$ shows that $u^T(X-Y^TZ^+Y)u\le1$. Yet, $u^T(X-Y^TZ^+Y)u$ is precisely $y^TRy$. Therefore $y^TRy\le1$. Conversely, if $y^TRy\le1$, put $u=D^{-1}y$ and $v=-Z^+Yu$ in $(1)$. Then $(2)$ shows that $x^TQx\le1$. Therefore $$ \{y:y^TRy\le1\}=\{y:y=Cx \text{ for some $x$ with $x^TQx\le1$}\}. $$ It remains to express $R$ in terms of $Q$ and $C$. Let $P=\pmatrix{0&0\\ 0&I_{n-m}}=I-C^+C$. Then \begin{align} R&=\pmatrix{(D^{-1})^T&0}\left[\pmatrix{X&Y^T\\ Y&Z}-\pmatrix{0&Y^T\\ 0&Z}\pmatrix{0&0\\ 0&Z^+}\pmatrix{0&0\\ Y&Z}\right]\pmatrix{D^{-1}\\ 0}\\ &=(C^+)^T\left[Q-QP(PQP)^+PQ\right]C^+\\ &=(C^+)^TQ^{1/2}\left[I-A(A^TA)^+A^T\right]Q^{1/2}C^+\quad(A=Q^{1/2}P)\\ &=(C^+)^TQ^{1/2}(I-AA^+)Q^{1/2}C^+\\ &=(C^+)^TQ^{1/2}\left[I-\left(Q^{1/2}(I-C^+C)\right)\left(Q^{1/2}(I-C^+C)\right)^+\right]Q^{1/2}C^+.\tag{4} \end{align}

---

Remark. Our formula $(4)$ has the following geometric interpretation. Basically, we want to find a semi-inner product $\langle\cdot,\cdot\rangle_m$ on $\mathbb R^m$ such that

1. $\langle Cx,Cx\rangle_m\le x^TQx$ for all $x\in\mathbb R^n$;
2. given any $y\in\mathbb R^m$, there exists some $x\in\mathbb R^n$ such that $y=Cx$ and $\langle Cx,Cx\rangle_m=x^TQx$.

Since $x^TQx=(Q^{1/2}x,\,Q^{1/2}x)$, where $(\cdot,\cdot)$ denotes the standard inner product on $\mathbb R^n$, an obvious strategy is to map $y\in\mathbb R^m$ to the vector $x=C^+y\in\mathbb R^n$ and define $\langle y,y\rangle_m$ as $(PQ^{1/2}x,PQ^{1/2}x)$ for some appropriate positive semi-definite matrix $P$. As the equation $Cx=y$ is solved by any $x\in C^+y+\ker(C)$, we want to pick a $P$ that is zero on $Q^{1/2}\ker(C)$. A natural choice is therefore to take $P$ as the orthogonal projection onto $\left(Q^{1/2}\ker(C)\right)^\perp$, i.e., $$ P=I_n-\left(Q^{1/2}(I_n-C^+C)\right)\left(Q^{1/2}(I_n-C^+C)\right)^+ \tag{4.5} $$ and define $$ \langle y,y\rangle_m=(PQ^{1/2}C^+y,PQ^{1/2}C^+y).\tag{5} $$ It is straightforward to verify that this semi-inner product does work. Given any $x\in\mathbb R^n$, let $y=Cx$. Since $PQ^{1/2}(I_n-C^+C)=0$, we have $PQ^{1/2}=PQ^{1/2}C^+C$. Therefore \begin{align*} \langle Cx,Cx\rangle_m &=\langle y,y\rangle_m\\ &=(PQ^{1/2}C^+y,PQ^{1/2}C^+y)\\ &=(PQ^{1/2}C^+Cx,PQ^{1/2}C^+Cx)\\ &=(PQ^{1/2}x,PQ^{1/2}x)\\ &\le(Q^{1/2}x,Q^{1/2}x)\quad\text{(because $P$ is an orthogonal projection)}\\ &=x^TQx.\\ \end{align*} Hence $x^TQx\le1$ implies that $\langle Cx,Cx\rangle_m\le1$.

Conversely, given any $y\in\mathbb R^m$, let \begin{cases} z=Q^{1/2}C^+y,\\ x=C^+y-(I_n-C^+C)\left(Q^{1/2}(I_n-C^+C)\right)^+z. \end{cases} Then $y=Cx$ and $ Q^{1/2}x =z-\left(Q^{1/2}(I_n-C^+C)\right)\left(Q^{1/2}(I_n-C^+C)\right)^+z =Pz $. Hence $$ \langle y,y\rangle_m =(PQ^{1/2}C^+y,PQ^{1/2}C^+y) =(Pz,Pz) =(Q^{1/2}x,Q^{1/2}x) =x^TQx. $$ Therefore, if $\langle y,y\rangle_m\le1$, then $y$ is indeed the image of some $x$ under $C$ such that $x^TQx\le1$.

Now, if we use the expression for $P$ in $(4.5)$ to write $(5)$ in matrix form, we get $(4)$.

Answer 2

One approach is as follows: we are trying to describe the set $$ U = \Big\{ Cx \mid x \in \mathbb{R}^n, x^{\rm T}Qx\le 1\Big\} = \\ \Big\{ y \mid \exists x \in \mathbb{R}^n \text{ s.t. } y = Cx \text{ and } x^{\rm T}Qx\le 1\Big\}. $$ Let $S$ denote an invertible matrix such that $S^{T}JS$, where $J$ has the same size as $Q$ and $J = \operatorname{diag}(I_r,0)$ ($r$ equal to the rank of $A$); such an $S$ exists by Sylvester's law of inertia. We note that $$ x^TQx = x^T(S^TJS)x = (Sx)^T J (Sx), $$ and $x^TJx = x_1^2 + \cdots + x_r^2$. Setting $v = Sx$, we can write $$ \Big\{ y \mid \exists x \in \mathbb{R}^n \text{ s.t. } y = Cx \text{ and } x^{\rm T}Qx\le 1\Big\} = \\ \Big\{ y \mid \exists v \in \mathbb{R}^n \text{ s.t. } y = CS^{-1}v \text{ and } v^TJv\le 1\Big\}. $$ Break $CS^{-1}$ into the blocks $$ CS^{-1} = \pmatrix{M_1& M_2}, $$ Break $v$ into $v = (v_1,v_2)$, where $v_1$ has length $r$. We have $$ U = \{M_1 v_1 + M_2 v_2 : \|v_1\| \leq 1\} = \operatorname{im}(M_2) + \{M_1 v_1 : \|v_1\| \leq 1\}. $$ Notably, $\operatorname{im}(M_2)$ is the image under $C$ of the kernel of $Q$.

Answer 3

Not an answer. Just some thoughts.

Update 1

In the first example, $\mathrm{rank}(R)=1$. Here I gave an example in which $\mathrm{rank}(R) > 1$.

2nd example: $n = 6$, $m = 4$, $\mathrm{rank}(Q) = 5$, $$Q = \left(\begin{array}{rrrrrr} 20 & -10 & 4 & 6 & -4 & -12\\ -10 & 17 & 6 & -5 & -1 & 6\\ 4 & 6 & 14 & -2 & -2 & 4\\ 6 & -5 & -2 & 5 & -5 & -2\\ -4 & -1 & -2 & -5 & 10 & 0\\ -12 & 6 & 4 & -2 & 0 & 20 \end{array}\right), $$ $$C = \left(\begin{array}{rrrrrr} -1 & 2 & 5 & -3 & 4 & -1\\ 3 & -3 & -2 & 4 & -5 & -4\\ -4 & 3 & 5 & 3 & 3 & 2 \end{array}\right),$$ $$R = \frac{1}{23902795}\left(\begin{array}{rrr} 7076120 & 3075640 & -1575100\\ 3075640 & 6201080 & -1235900\\ -1575100 & -1235900 & 413086 \end{array}\right). $$

Let $$S = \{Cx : \ x\in \mathbb{R}^n, \ x^\mathsf{T}Qx \le 1\}$$ and $$S_1 = \{y : \ y\in \mathbb{R}^m, \ y^\mathsf{T}Ry \le 1\}.$$

It is not difficult to prove that $S \subseteq S_1$. I $\color{blue}{\textrm{GUESS}}$ that $S = S_1$. Are there nice algorithms to check it?

Previously written

Consider an example: $n = 6$, $m = 4$, $\mathrm{rank}(Q) = 3$, $$Q = \left(\begin{array}{rrrrrr} 6 & -6 & 5 & -3 & 0 & -1\\ -6 & 8 & -6 & 6 & 0 & 0\\ 5 & -6 & 5 & -4 & -2 & 1\\ -3 & 6 & -4 & 6 & 0 & -1\\ 0 & 0 & -2 & 0 & 12 & -8\\ -1 & 0 & 1 & -1 & -8 & 6 \end{array}\right), $$ $$C = \left(\begin{array}{rrrrrr} -3 & -1 & 3 & 4 & 1 & 1\\ 0 & 4 & 4 & -3 & 3 & -3\\ 2 & -1 & 3 & -4 & 2 & 4\\ -3 & -2 & -5 & -3 & -4 & 2 \end{array}\right),$$ $$R = \frac{1}{100580862}\left( \begin{array}{r} 1266 \\ 1326 \\ 1744 \\ 3007 \\ \end{array} \right)\left( \begin{array}{r} 1266 \\ 1326 \\ 1744 \\ 3007 \\ \end{array} \right)^\mathsf{T}. $$ Let $$S = \{Cx : \ x\in \mathbb{R}^n, \ x^\mathsf{T}Qx \le 1\}$$ and $$S_1 = \{y : \ y\in \mathbb{R}^m, \ y^\mathsf{T}Ry \le 1\}.$$

It is not difficult to prove that $S \subseteq S_1$. I $\color{blue}{\textrm{GUESS}}$ that $S = S_1$. Can someone prove or disprove it (at least numerically)?

I do not know a nice way to 'prove' or disprove (at least numerically) $S = S_1$ even for simpler examples.

Remark: I also check OP's result, that is, $$R' = (I-P^{+}P) Y (I-P^{+}P), \quad P = (I-Q^{+}Q)C^\mathsf{T}, \quad Y = \big(CQ^{+}C^\mathsf{T}\big)^{+}.$$ Let $S_2 = \{y : \ y\in \mathbb{R}^m, \ y^\mathsf{T}R' y \le 1\}$. I proved that $S \nsubseteq S_2$, so I think that OP's result is not true (if I am not wrong).

Answer 4

It is known that $R=(CQ^{-1}C^{\rm T})^{-1}$ for a positive definite $Q$.

I am going to find an answer for a positive semidefinite $Q$ as a limit

$$ R = \lim_{\varepsilon \to 0} \Big(C(Q+\varepsilon I)^{-1}C^{\rm T}\Big)^{-1}, $$

which, I think, can be justified by the fact that $x \mapsto Cx$ is continuous.

Denote $$ M := Q^{1/2}, \quad N := I-C^{+}C. $$

Using Woodbury matrix identity one can write

$$ (Q+\varepsilon I)^{-1} = (\varepsilon I + MM)^{-1} = \frac{1}{\varepsilon}I-\frac{1}{\varepsilon}M(I+\frac{1}{\varepsilon}MM)^{-1}\frac{1}{\varepsilon}M $$

and

$$ \star \, := \Big(C(Q+\varepsilon I)^{-1}C^{\rm T}\Big)^{-1} = \Big( \frac{1}{\varepsilon}CC^{\rm T}-\frac{1}{\varepsilon}CM(I+\frac{1}{\varepsilon}MM)^{-1}\frac{1}{\varepsilon}MC^{\rm T}\Big)^{-1}. $$

Taking advantage of $C$ being full row rank ($CC^{\rm T}$ being invertible), use Woodbury matrix identity again to obtain

$$ \star = \varepsilon (CC^{\rm T})^{-1} + (CC^{\rm T})^{-1} CM \Big( I+\frac{1}{\varepsilon}M \big(I - C^{\rm T}(CC^{\rm T})^{-1}C \big) M \Big)^{-1} MC^{\rm T} (C C^{\rm T})^{-1}. $$

Note that

$$ C^{\rm T} (C C^{\rm T})^{-1} = C^+, \quad (I - C^{\rm T}(CC^{\rm T})^{-1}C) = N = N^2, $$

and rewrite $\, \star \,$ as

$$ \star =\varepsilon (CC^{\rm T})^{-1} + C^{+ \rm T} M \Big( I + \frac{1}{\varepsilon}M NN M\Big)^{-1}MC^+. $$

Use Woodbury matrix identity again to obtain

$$ \star =\varepsilon (CC^{\rm T})^{-1} + C^{+ \rm T} M \Big( I-MN \big( \varepsilon I + NMMN \big)^{-1} NM \Big)MC^+. $$

Then take the limit as $\varepsilon \to 0$ and apply the limit relation to get

$$ R = C^{+ \rm T} M \Big( I-MN \big( MN \big)^+ \Big)MC^+. $$

Substitute $M$ and $N$ to obtain the final answer

$$ R = C^{+ \rm T} Q^{1/2} \Big(I-Q^{1/2}(I-C^+C)\big( Q^{1/2}(I-C^+C) \big)^+\Big)Q^{1/2}C^+. $$