Re: How can I solve this kind of linear system Message #7 Posted by Rodger Rosenbaum on 25 Nov 2007, 10:51 a.m., in response to message #1 by Alexander DeLarge
This is an interesting problem.
The solution to your problem can be written:
[ 0 3 0 ] + t*[ 1 2 1 ]
or:
[ 1 1 1 ] + t*[ 1 2 1 ]
That is, a particular solution vector plus some multiple of another vector. That second vector is in the null space of the coefficient matrix, meaning that the coefficient matrix times [ 1 2 1 ] gives [ 0 0 ]. And, therefore, the coefficient matrix times any multiple of [ 1 2 1 ] also gives [ 0 0 ]. So any multiple of [ 1 2 1 ] can be added to a solution vector and the result is still a solution vector.
It just so happens, mirabile dictu, that the HP48G and descendants can give the solution you want. All you need to do is to find a vector in the null space of the coefficient matrix. You do this by placing the coefficient matrix on the stack and executing SVD. Three items will be returned to the stack. The second item, the V matrix, has a unit length vector in the null space as its last row. The elements of that vector aren't integers, but in this case they can be made integers by dividing the vector by its first element.
Keep in mind that it's only because this system is underdetermined that it's guaranteed to have a nonempty null space. If it were fully determined it might not have a nonempty null space.
Here's a little program (not necessarily optimized) that can do the entire job. Just put the coefficient matrix on level 2 of the stack and the column matrix on level 1 and execute PARAM.

PARAM
<< OVER LSQ TRN >ROW DROP SWAP DUP SIZE 2 GET
SWAP SVD ROT DROP2 SWAP ROW SWAP DROP
DUP 1 COL SWAP DROP / >>

Just do:
2: [[ 1 1 1 ]
[ 1 2 3 ]]
1: [[ 3 ]
[ 6 ]]
PARAM
and see:
2: [ 1. 1. 1. ]
1: [ 1. 2. 1. ]
On level 2 is a (smallest Euclidean norm) solution vector, and on level 1 is a vector in the null space of the coefficient matrix. Press  and see [ 0. 3. 0. ], the solution vector you posted. This vector plus any multiple of the vector that was on level 1 is another solution.
When you still have:
2: [ 1. 1. 1. ]
1: [ 1. 2. 1. ]
on the stack, press 7 * + and see [ 8. 13. 8 ], another solution, and so forth.
It may not always be possible to convert the last row of the V matrix (from the SVD) to a vector of integers, but even if not, it still provides the parameterized solution you want.
Try:
2: [[ 1 1 1 ]
[ 7 3 5 ]]
1: [[ 3 ]
[ 6 ]]
PARAM
and see:
2: [ 1.25 3.25 1. ]
1: [ 1. 1. 2. ]
In this case, the null space vector did convert to a vector of integers. You could enlarge the program to test if all the elements of the vector can be made integers, and if not, just keep the last row of the V matrix as it was.
Edited: 25 Nov 2007, 10:54 a.m.
