Note that a solution need not always exist for all n.
When n==1, and so A is a 1x1 matrix, it is completely known. So unless you have A = sqrt(S), no solution exists at all.
When n==2, there are 3 unique pieces of information in S, but only 2 unknowns. This makes the problem over determined, and so there is likely no exact solution.
When n==3, things get a little better. there we have 6 distinct pieces of information in S, and 6 unknowns that make up rows 2 and 3 of A. That MAY allow a solution. If a solution exists, it will be unique.
When n > 3, there are n*(n+1)/2 distinct pieces of information in S, and n*(n-1) unknowns you can try to find. As long as n>3, we have:
simplify(n*(n-1) - n*(n+1)/2)
ans = And that is always positive as long as n is strictly greater than 3. As such, there are only potentially infinitely many solutions when n>3.
Next, look at this from the other way around. Consider the matrix S. What do we know about it? S MUST be SPD, else we cannot find A such that A'*A==S, since A'*A will bre SPD. And that suggests we look at the eigenvalue decomposition of S.
S = P*D*P'
What does that tell us about A? More importantly, what can it tell us about the singular value decomposition of A? Yes, I know, we don'rt know A, not yet. So we cannot possibly know the SVD of A. But if we think about it, consider the svd of A.
A = U*S_A*V'
then
A'*A = U*S_A*S_A'*U' = P*D*P'
But S_A is diagonal. and that tells us that the SINGULAR values of A will be the square roots of the EIGENVALUES of S.
Next, I'll give an example, where we know no solution can possibly exist, even for large n.
S = randn(5);S = S'*S
S =
4.4258 2.7151 1.4157 -1.6872 -0.9656
2.7151 4.2320 0.4269 -2.0232 -0.9481
1.4157 0.4269 7.6741 -0.9907 -3.5518
-1.6872 -2.0232 -0.9907 4.8634 0.4472
-0.9656 -0.9481 -3.5518 0.4472 3.5497
<mw-icon class=""></mw-icon>
<mw-icon class=""></mw-icon>
S is known to be positive definite. It has eigenvalues of
eig(S)
ans =
1.0958
1.8454
3.2125
7.1567
11.4346
<mw-icon class=""></mw-icon>
<mw-icon class=""></mw-icon>
Next, I'll just make up a vector for A(1,:).
Next, I'll make the simple claim, that if any row of the matrix A has norm x, then at least one of the singular values of A will be at least as large as x. (You should be able to prove that as a homework assignment.)
So clearly, NO solution can exist for the case where A has first row A1, since 14.4222^2 > 11.4346.
Next, can we say any more about the singular values of the matrix A? What if A has a special property? For example, suppose we chose A such that
A = [A1;U]
where the rows of the matrix U are constrained to lie in the nullspace of the vector A1? What then would it tell you about the svd of A?
HINT: If you follow what I just said, and extend it just a bit, it should give you a constructive way to compute A. I'll wait for a day to see if you can take that idea and use it, before showing what I think is a method to construct A, but it would only work under certain specific circumstances, that would limit the possible choices for your first row. I might even be able to show that says something about when a solution can or cannot exist.