MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
What if your orthogonal matrix is the identity matrix? Then the left side is just $J_r \circ S$, which cannot equal $I_r$. – Will Sawin Jun 22 '12 at 20:29
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. – user11870 Jun 22 '12 at 20:36
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. – user11870 Jun 22 '12 at 20:41
@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. – Noah Stein Jun 22 '12 at 20:47
I see. But if so, I want to point out that the left-hand side is not $J_r\circ S$. – user11870 Jun 22 '12 at 21:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.