How to efficiently solve a system with an infinity number of solutions?

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.

[Torsten]

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

[Marco Brianti]

Yes, thank you. Otherwise the system does not have any solution.

[David Goodmanson]

Hi Marco, this would probably be easier if you knew the first column of A rather than the first row. As it is, there is at least one restriction on that known first row. Denoting that vector by a, then abs(a').^2 has to be smaller than diag(S) term-by-term.

[Marco Brianti]

The problem can be isomorphically re-written by knowing the first column of A, rather than the first row. The rest is the same. Also assume that the problem is well-defined, in the sense that for n>3 a solution always exist. If you know how to deal with this case, please let me know. Many thanks

[David Goodmanson]

Could you explain how the problem can be isomorphically rewritten with a known first column of A, while still preserving the form of the expression A' A = S?

Answer 1

[John D'Errico]

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)

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.

n = 5; % sufficiently large
S = randn(5);S = S'*S

S = 5x5

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 = 5x1

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,:).

A1 = [2 3 5 7 11];
norm(A1)

ans = 14.4222

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.

[Marco Brianti]

Dear John, many thanks for the detiled analysis and I agree with your points. Please assume the problem to be such that n > 3 and the first row of A is well-behaved, in the sense that it allows for an infinite number of solutions to the system: A'*A = S. If you can help me on how to get a solution to this problem without employing a numerical solution like "fsolve", it would be great. Many thanks