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

4 views (last 30 days)
Marco Brianti on 7 May 2024
Edited: David Goodmanson on 8 May 2024
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.
Marco Brianti on 8 May 2024
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 on 8 May 2024
Edited: David Goodmanson on 8 May 2024
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?

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)
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 on 8 May 2024
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

### Categories

Find more on Matrix Indexing in Help Center and File Exchange

R2024a

### Community Treasure Hunt

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

Start Hunting!