Linear algebra challenge answers

My purpose in posting the challenges is to increase awareness of the
Singular Value Decomposition (SVD), a function found on the HP48G and HP49G
series calculators.

The book, "Linear Algebra and its Applications", by Gilbert Strang is a
good reference for those who want more information. Another very nice
reference on the web is the paper
http://www.american.edu/academic.depts/cas/mathstat/People/kalman/pdffiles/svd.pdf

The SVD can be applied to any matrix, square or rectangular, real or
complex. The result of the decomposition as traditionally described in
texts is three matrices, U, S, and V (the texts use the capital greek
letter sigma instead of S; also the matrix V is usually the transpose of
the V returned by the HP49G+, but I will describe what the calculator
does).

U and V are orthogonal matrices; that is, they are square matrices whose
columns and rows are of unit length, and the rows and columns are linearly
independent of one another (orthogonal matrices have the property that when
THEY multiply a vector, they don't change its length). In texts, the matrix
S is a diagonal matrix with the singular values on the main diagonal, and
zeroes elsewhere. From an m x n matrix initially on the stack, the
calculator returns on the stack, U V S, with S as a vector rather than a
diagonal matrix; the singular values are sorted in decreasing order in the
vector S. The number of singular values is the lesser of m and n, and some
of them may be zero.

Given an input matrix A, the relationship that holds is given by this
expression: A = U * DIAG(S) * V. If the input matrix, A, is an m x n
dimensional matrix, then the U matrix is m x m, the V matrix is n x n, and
the vector S returned by the calculator must be converted to an m x n
diagonal matrix with the singular values on the main diagonal before the
multiplication can be carried out.

I like to create a special directory for playing around with the SVD
containing the variables A, B, U, V, and S. I also like to have some
little programs there. Make sure flag -54 is set when using them.

Some programs used are as follows (sometimes I leave results on the stack,
sometimes not, with no particular organizational scheme in mind!):

->SV (this program computes the Singular Value Decomposition of a matrix on
level 1 of the stack, and leaves the results, U V S, on the stack. You
could just type SVD each time you need it, but this gives it with just a
single keystroke)

<< SVD >>

SV-> (this program expects the same objects on the stack that SVD would
leave there, namely U V S. It then makes a suitable diagonal matrix from S
and multiplies the 3 objects, re-creating the matrix whose SVD was in U, V
and S.)

<< 3 PICK SIZE OBJ-> DROP2 3 PICK SIZE OBJ-> DROP2 2 ->LIST DIAG-> SWAP * *


PSU (The product TRANSPOSE(V) * DIAG(1/s) * TRANSPOSE(U) is computed. This
program expects an integer N on the stack. It then recalls U, V, and S from
the variables and computes a pseudoinverse for the matrix whose SVD is
stored in those variables. This pseudoinverse can be rank reduced by means
of the integer initially on the stack when PSU is invoked. What it does is
to zero N of the reciprocals of the singular values starting with the
smallest and working toward the largest. If the matrix SVD stored in the
variables is of a square matrix, and if N is 0, then the ordinary inverse
is returned.)

<< -> N << U TRN V TRN S OBJ-> OBJ-> DROP ->LIST 1E-499 ADD INV OBJ-> 1
SWAP 2 ->LIST ->ARRY DUP SIZE OBJ-> DROP N - 2 ->LIST { 1 1 } SWAP SUB 3
PICK SIZE OBJ-> DROP2 3 PICK SIZE OBJ-> DROP2 SWAP 2 ->LIST DIAG-> ROT * *



Cond (this program computes the condition number of a matrix on the stack
as the ratio of the largest to the smallest singular values. Be sure to
spell the name with a capital "C" and lower case "ond" so as not to
conflict with the built-in COND command.)

<< SVL DUP 1 GET SWAP DUP SIZE 1 GET GET / >>

Some properties of the singular values of a matrix:

1. The Euclidean norm is the square root of the sum of the squares of the
singular values (the ABS function applied to the vector S, in other words).
The spectral norm is just the largest singular value; thus we see that the
spectral norm is always less than or equal to the Euclidean norm.

2. The determinant of a square matrix is the product of its singular
values. Thus, if any of the singular values is zero, the square matrix is
singular; if any singular value is very small compared to the largest
singular value, then the matrix is nearly singular. For a non-square
matrix, if any of the singular values is zero, we say that the matrix is
rank deficient. Rank deficiency carries similar implications for a
non-square matrix as does singularity for a square matrix.

3. The (Euclidean) distance to the nearest singular matrix (in the case of
a square matrix) IS the smallest singular value.

4. The condition number of a matrix is the ratio of the largest to
smallest singular value.
-----------------------------------------------------------
Type the matrix from the first challenge:

[[ 1.0001 1 1 1 ]
[ 2 2.0001 2 2 ]
[ 3 3 3.0001 3 ]
[ 4 4 4 4.0001 ]

and store it in the variable A.

Now, recall the matrix A and press ->SV; store the objects U V S which
are on the stack into their respective variables. Recall U V S to the
stack and press the silver down arrow key to enter the matrix writer. Edit
the S vector so that the smallest singular value is zero, and return the
vector to the stack. We now have on the stack the SVD of a matrix with a
zero singular value, so the matrix whose SVD this is, must be singular. To
get this matrix back, press SV->. This is the answer to the first
challenge.

The answer to the second challenge is simply the last row in the V matrix
from the SVD of matrix A. That row is a vector with length 1, and of all
such vectors used to postmultiply A, when this vector is used the
(Euclidean) norm of the result is the smallest possible.

With V on the stack, enter the matrix writer, press NXT once and press
-ROW three times, then ENTER to return the last row to the stack.
Type TRN A SWAP * to postmultiply A by that last row from V. Now press ABS
to get the norm of the result. This number is the smallest possible for
postmultiplication by any unit length 4 element vector. And, in fact, you
will note that this number is equal to the smallest singular value of the
matrix A! Premultiplying the A matrix with the transpose of the last
column of the U matrix gives the same result. Mirabile Dictu!

I made the third challenge too easy. I wanted to require the use of the
SVD, but it's possible to solve it without the SVD. Here's how:

Recall A to the stack 3 times. Type ABS / to create a matrix of unit
(Euclidean) size. This matrix has no components orthogonal to the matrix
A; this is the important part. Now press - to subtract this unit matrix
from A; this matrix is the solution to the challenge. Type ABS to see its
size. Can you find a way to use the SVD to solve the problem?

I'm going to wait a little longer to give the solution to the fourth
challenge to see if anyone will step up.

I'll post some more about the SVD later.
.

Relevant Pages

  • Linear algebra challenge answers
    ... Singular Value Decomposition (SVD), a function found on the HP48G and HP49G ... From an m x n matrix initially on the stack, ... The determinant of a square matrix is the product of its singular ...
    (comp.sys.hp48)
  • Re: SVD when calculated for a corpus of similar category?
    ... Peter Spellucci wrote: ... Suppose i compute SVD for a huge corpus ... >singular values in the diagonal matrix S arranged in descending order ...
    (sci.math.num-analysis)
  • Re: SVD when calculated for a corpus of similar category?
    ... Suppose i compute SVD for a huge corpus ... >singular values in the diagonal matrix S arranged in descending order ...
    (sci.math.num-analysis)
  • Re: Writing a matrix as a multiplication of two vectors
    ... this matrix will be highly singular with a rank of only 1. ... If A, an m X n matrix has rank r, it can be represented by a weighted ... The weights and vectors are called the singular ... functions SVD and SVDS. ...
    (comp.soft-sys.matlab)
  • Re: ? determine major singular pair
    ... The are methods to determine the major eigenpair of a square matrix A, ... singular pair of a rectangular matrix? ... a square matrix's major eigenpair to get singular pair. ...
    (sci.math.num-analysis)