Clear Filters
Clear Filters

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

4 views (last 30 days)
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.
  5 Comments
Marco Brianti
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
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?

Sign in to comment.

Answers (1)

John D'Errico
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.
  1 Comment
Marco Brianti
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

Sign in to comment.

Products


Release

R2024a

Community Treasure Hunt

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

Start Hunting!