Alternative to Choleski Decomposition for Correlation Matrix

Question

Let $\Sigma$ be a correlation matrix, ie. symmetric. The Choleski decompositon gives upper triangular $A$ such that $A^TA = \Sigma$. Instead of upper triangularity, we are looking for $A$ that is not upper triangular, instead having each column sum to the same value and each entry $ \ge 0$. I've already managed to get this working in two dimensions with a simple solver, but three and up seem challenging. Is there a known method that would produce the desired matrix?

The goal is to apply a correlation matrix to random vectors with a "balanced" distortion effect on the points, rather than leaving the first vector the same and heavily altering the last few.

Answer 1

For the purposes of this answer I will ignore the condition of constant column sums. You ask for a matrix $A$ with $A^TA = \Sigma$ and $A\geq 0$ element wise. Such a matrix need not exist. For example, its existence would imply that $\Sigma\geq 0$ elementwise. Even if this is the case, testing for existence of such an $A$ is NP-hard: this is the problem of checking whether a matrix is completely positive (see this paper).

Answer 2

While the question of positiveness was answered by Noah the other question (of equal column- (or row?) sums in A) can be dealt with the concept of Givens-rotation, where you iteratively rotate pairs of columns (or rows?) to a predefined optimization criterion. The angle for the pairwise column-rotations must then be determined by a criterion which minimizes the the difference of the sums. This should be similar to the centroid-rotation, but where we compute the maximizing criteria in the centroid-rotation we need the minimizing criteria now. Perhaps I can support this with an example later....
[update] I've got the rotation criterion for each elementary Givens-rotation. Let's -for my convenience- assume, that by $ \Sigma = A \cdot A^T$ the cholesky-factor $A$ of $ \Sigma$ is lower triangular. Then we iterate pairwise column-rotations in $A$ to pairwise and finally to completely equal column-sums. One such pairwise rotation is called "elementary Givens rotation".

The criterion-formula for the sought c as cosine of the rotation-angle and s as sine of the rotation-angle where x denotes the column with the lower index ("to the left") and y denotes the column with the higher index ("to the right") of one pairwise rotation and k goes over all row-indices is: $$ \sum_k (x_k \cdot c - y_k \cdot s ) = \sum_k (x_k \cdot s + y_k \cdot c )$$ From this we can compute c and s as $$ c \cdot \sum x_k - s \sum y_k = s \cdot \sum x_k + c \cdot \sum y_k \\ c \cdot \sum (x_k - y_k) = s \sum (y_k + x_k) \\ c = { a \over z } \qquad s = { b \over z } \\ \text{where } a=\sum (y_k + x_k) \qquad b=\sum (x_k - y_k) \qquad z = \sqrt{a^2+b^2}$$

Then the (elementary Givens-) rotation of the columns X and Y is $$ X' = X\cdot c - Y \cdot s \qquad Y'=X\cdot s + Y \cdot c $$

One iteration-pass is then to apply this computation to all combinations of pairs of columns, where only always the X column means that of the smaller index.
Here is one example with a random correlation matrix, its initial cholesky-factor A and the vector SU containing the column-sums (which shall be made equal by the rotations):

        |   1,0000    0,0000      0,0000      0,0000 |
        |   0,7139    0,7003      0,0000      0,0000 |
 A=     |   0,9022    0,3439      0,2603      0,0000 |
        |   0,5865    0,6970      0,3367      0,2382 |
            =====================================     
SU=     |   3,2026    1,7412      0,5970      0,2382 |

One rotation on the leftmost columns gives

        |   0,9590    0,2835      0,0000      0,0000 |
        |   0,4861    0,8739      0,0000      0,0000 |
  A=    |   0,7677    0,5856      0,2603      0,0000 |
        |   0,3649    0,8347      0,3367      0,2382 |
==========================================================
 SU=    |   2,5777    2,5777      0,5970      0,2382 |

and after 5 complete iteration passes I get

        |   0,7133    0,0320      0,4429      0,5422 |
        |   0,4761    0,7200      0,2739      0,4241 |
 A=     |   0,5372    0,3850      0,6116      0,4349 |
        |   0,1242    0,7138      0,5225      0,4495 |
 =========================================================
 SU=    |   1,8508    1,8508      1,8508      1,8508 |       

where we see, that all column-sums are equal.