5
$\begingroup$

Let $P\in \mathbb{R}^{n\times r}$ be a submatrix (which consists of the first $r$ columns) of an arbitrary $n\times n$ orthogonal matrix ($1 < r < n$). Let $I_n$ denote the $n\times n$ identity matrix and $E_n$ denote the $n\times n$ matrix with all entries being $1$. Let $J_n := E_n -I_n$. Consider the following linear system $$P^T(J_n\circ PSP^T)P = I_{r},$$ where ''$\circ$'' denotes the Hadamard product.

It can be shown that when $S$ is restricted to be an $r\times r$ symmetric matrix, this linear system always has a unique solution.

Question: Is the unique solution $S$ always positive definite?


FYI: Illustration of the uniqueness of the solution.

Let $\text{vec}(\cdot)$ denote the vectorization operator by stacking the columns of a matrix into a single column and $\text{vech}(\cdot)$ denote the vectorization operator for symmetric matrices by stacking only diagonal and lower-diagonal entries column by column. Let ''$\otimes$'' denote the Kronecker product. The linear system when restricted to the symmetric matrix cone can be rewritten as $$[H_r(P\otimes P)^T \text{Diag}(\text{vec}(J_n))(P\otimes P) G_r] \text{vech}(S) = \text{vech}(I_r),$$ where $\text{Diag}(\text{vec}(J_n))$ is an $n^2 \times n^2$ diagonal matrix with $n^2-n$ nonzero diagonal entries $1$, $P\otimes P \in \mathbb{R}^{n^2 \times r^2}$ is of full-rank, $H_r \in \mathbb{R}^{r(r+1)/2\times r^2}$ and $G_r \in \mathbb{R}^{r^2\times r(r+1)/2}$ are full-rank matrices such that for any $r\times r$ symmetric matrix $X$, $$\text{vech}(X) = H_r\text{vec}(X), \quad \text{vec}(X) = G_r\text{vech}(X), \quad \forall \ r\times r \ \text{symmetric matrix} \ X.$$ Notice that $n^2-n\geq r^2$ for any $1 < r < n$. Since $P\otimes P$ is the first $r^2$ columns of an orthogonal matrix, $\text{Diag}(\text{vec}(J_n)) (P\otimes P)$ is of full rank and thus we obtain the uniqueness.

$\endgroup$
  • 2
    $\begingroup$ What if your orthogonal matrix is the identity matrix? Then the left side is just $J_r \circ S$, which cannot equal $I_r$. $\endgroup$ – Will Sawin Jun 22 '12 at 20:29
  • 1
    $\begingroup$ Assumption: $1<r<n$. So $P$ cannot be the identity matrix. If so, we cannot have $n^2-n\geq r^2$ in the last line but two. $\endgroup$ – user11870 Jun 22 '12 at 20:36
  • 1
    $\begingroup$ I believe the answer of the question is true based on random generated numerical tests. Numerical tests also show that it should be true if the term $I_r$ on the right-hand side is replaced by any diagonal matrix with positive diagonal entries. $\endgroup$ – user11870 Jun 22 '12 at 20:41
  • $\begingroup$ @wmmiao: I believe Will Sawin's point was to consider what happens if the "arbitrary orthogonal matrix" you mentioned was the identity, making $P$ the first $r$ columns of the identity. $\endgroup$ – Noah Stein Jun 22 '12 at 20:47
  • 1
    $\begingroup$ I see. But if so, I want to point out that the left-hand side is not $J_r\circ S$. $\endgroup$ – user11870 Jun 22 '12 at 21:02
0
$\begingroup$

I think the answer is yes. Write $$P^\mathrm{t}(J_n \circ PSP^\mathrm{t})P=P^\mathrm{t}(PSP^\mathrm{t}-I_n\circ PSP^\mathrm{t})P=S-P^\mathrm{t}(I_n \circ PSP^\mathrm{t})P$$ so the solution satisfies $$(1)\quad S=I_r+P^\mathrm{t}(I_n \circ PSP^\mathrm{t})P.$$ Suppose $S$ is symmetric and let $Sv_j=\lambda_j v_j$ for $j=1,2,\ldots,r$ be an orthonormal eigenbasis of $\mathbb{R}^r$. Then $$I_n \circ PSP^\mathrm{t}=\sum_{ij}\lambda_j (e_i e_i^\mathrm{t})\circ (Pv_j v_j^\mathrm{t}P^\mathrm{t})=\sum_{ij}\lambda_j (e_i \circ Pv_j)(e_i \circ Pv_j)^\mathrm{t}$$ $$=\sum_{i} (e_i e_i^\mathrm{t}) \sum_j \lambda_j (P_i \cdot v_j )^2.$$ Furthermore $$\left\langle v_i, P^\mathrm{t}(I_n \circ PSP^\mathrm{t})Pv_i\right\rangle = \left\langle Pv_i, (I_n \circ PSP^\mathrm{t})Pv_i \right\rangle\geq \|v_i\|^2\min_i \sum_j \lambda_j(P_i \cdot v_j )^2$$ which establishes that the smallest eigenvalue of $P^\mathrm{t}(I_n \circ PSP^\mathrm{t})P$ is no larger than the smallest eigenvalue of $S$. Therefore, if $S$ has a negative eigenvalue, the statement (1) leads to a contradiction. I think this means that $S$ and $S-I_r$ are positive semidefinite, which would imply that $S$ is positive definite. A similar argument would apply if $I_r$ were replaced by a different positive definite matrix.

$\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.