ans =

You forgot to add the restriction that S has to be positive semidefinite.

4 views (last 30 days)

Show older comments

Consider A to be a square matrix of size n and S to be a symmetric square matrix of size n. I know the first row of A and I know each element in S. I need to find the remaining elements (from row 2 to row n) of A such that A'A = S. This system allows an infinite number of solutions and I am not interested in a particular solution (any of them is fine). Does it exist an efficient procedure to find one among these solutions? In other words, I do not want to use an "fsolve" procedure because it is computationally too demanding. I would like to find a solution in the same spirit of chol(S)'*chol(S) = S. Nevertheless, chol(S) does not work because does not guarantee that the first row of A is the one I need. For another similar problem, I remember that null(A(1,:)) was useful. The problem is that [A(1,:); null(A(1,:))]'*[A(1,:); null(A(1,:))] = eye(n) and I need the right-hand side to be equal to S (instead of eye(n)).

I hope the problem is clear. Many thanks for the help.

David Goodmanson
on 8 May 2024

Edited: David Goodmanson
on 8 May 2024

John D'Errico
on 7 May 2024

Edited: John D'Errico
on 7 May 2024

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:

syms n

simplify(n*(n-1) - n*(n+1)/2)

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.

n = 5; % sufficiently large

S = randn(5);S = S'*S

S is known to be positive definite. It has eigenvalues of

eig(S)

Next, I'll just make up a vector for A(1,:).

A1 = [2 3 5 7 11];

norm(A1)

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.

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!