9
$\begingroup$

Hello,

Let $X'X$ be a positive definite matrix and let $\mathbf{1}$ denote the vector of ones.

I'm hoping to construct a positive, diagonal matrix $W$ such that $$(W X'X W) \mathbf{1} = \mathbf{1}$$

$X$ and $W$ are all assumed to have real-valued entries, and $X'$ denotes the transpose of $X$.

I don't, yet, have a proof that such a matrix $W$ always exists, but strongly suspect it. Any ideas on algorithms, proofs, or counter-examples would be gratefully received.

The problem arises from work in statistics.

thanks,

David.

Improve this question
$\endgroup$
5
  • $\begingroup$ You probably already know this, but the vector of all ones is an eigenvector of a matrix $M$ if and only if the rows of $M$ all have the same sum. So you want to try to find your diagonal matrix $W$ so that the row sums of $WX'XW$ are all one. (Also, you should make it clear what you mean by $X'$; is this the transpose or the conjugate transpose, i.e. are you working over $\mathbb{R}$ or $\mathbb{C}$?) $\endgroup$
    – MTS
    Jan 12, 2013 at 22:12
  • $\begingroup$ That this is true for 2 times 2 matrices :-) $\endgroup$
    – Alexandre Eremenko
    Jan 12, 2013 at 22:14
  • $\begingroup$ @MTS: I'm assuming real-valued entries, thx. Also, by symmetry, we will also have that WX'XW has columns that sum to one. It can have negative entries, though, so need not be doubly-stochastic. $\endgroup$
    – David Bryant
    Jan 12, 2013 at 22:58
  • 2
    $\begingroup$ There's a theorem that indecomposible nonnegative matrices can be rescaled (using separate row and column scalings) to become doubly stochastic. The proof is not trivial. I don't know if that can help, but it feels similar. $\endgroup$
    – Brendan McKay
    Jan 13, 2013 at 3:04
  • $\begingroup$ I believe I have a proof for $X$ nonnegative. Consider the simplex of diagonal matrices $W$ with nonnegative entries up to scaling, and the simplex of vectors $V$ with nonnegative entries up to scaling. The map $V= WX'XW$ sends each $k$-cell of the first simplex into the corresponding $k$-cell of the second simplex, since if some of the coordinates of $W$ are $0$ then some of the coordinates of $V$ are $0$. Every such map on simplices must be surjective, because it has a boundary-preserving homotopy to the standard one, by induction. $\endgroup$
    – Will Sawin
    Jan 13, 2013 at 4:22

2 Answers 2

Reset to default
4
$\begingroup$

Consider the simplex of nonzero diagonal matrices W with nonnegative entries up to scaling, and the simplex of nonzero vectors V with nonnegative entries up to scaling.

There is a map, $V=\max(WX′XW\mathbf 1,0)$, from the first simplex to the second, with $\max(a,0)$ interpreted entrywise. This is well-defined because $WX'XW\mathbf 1$ always has some positive entry, because the sum of its entries is $1'W X' X W1$, with $W1$ a nonzero vector and $X'X$ positive-definite.

This map clearly sends each k-cell of the first simplex into the corresponding k-cell of the second simplex, since if some of the coordinates of $W$ are $0$ then some of the coordinates of $V$ are $0$.

Every such map on simplices must be surjective. This is because the map from the boundary sphere of one simplex to the boundary sphere of the other is degree one, because every such map on simplices has a boundary-preserving homotopy to the standard isomorphism between those simplices, by induction.

So there is some $W$ such that $\max(WX′XW\mathbf 1,0)=\mathbf 1$. So $WX'XW\mathbf 1=\mathbf 1$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks heaps! My topology is a bit weak so I don't fully follow the proof of surjectivity, but I'll work at it and try to use it as the basis of a constructive proof. Thanks again. -David. $\endgroup$
    – David Bryant
    Jan 13, 2013 at 8:38
3
$\begingroup$

The relevant reference is

Marshall, A. and Olkin, I. Scaling of Matrices to Achieve Specified Row and Column Sums. Numerische Mathematik 12, 83-90 (1968)

who prove the result in the affirmative for positive definite matrices (and some generalizations). The proof is elegant and construction: the diagonal matrix can be found by minimizing a particular constrained optimization problem.

There is a good discussion of the problem and its generalizations in

Johnson, C.R. and Reams, R. Scaling of symmetric matrices by positive diagonal congruence. Linear and Multilinear Algebra, 57(2) (2009) 123-140.

-David.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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