 The Museum of HP Calculators

HP Forum Archive 18

 Re: "Ask Marilyn!" (Rank-deficient matrices and the HP-15C)Message #3 Posted by Rodger Rosenbaum on 29 Jan 2008, 8:22 p.m.,in response to message #2 by Karl Schneider Quote: Readers -- In the vein of what we've been discussing, a modest logic/algebra problem was given in the "Ask Marilyn" column of today's (January 27, 2008) Parade magazine, which is a Sunday-newspaper insert in the US. A reader submitted the following mild "brain teaser": [/italic] The answer is 21387. It is best solved by some basic algebraic-equation setup and logic. Discussion and comment is available at http://www.parade.com/articles/editions/2008/edition_01-27-2008/Ask_Marilyn. Now, if one were to set this up as a linear-algebra problem, one would obtain the system A N b [ 1 1 -1 0 0][n1]  [ 0 1 2 0 -1][n2]  [-1 2 0 0 0][n3] =  [ 4 0 0 -1 0][n4]  [ 0 -1 0 1 -1][n5]  A is singular, with a rank of 4. So, the set of all real-valued possible solutions lie on a line in five-dimensional space. (If A were nonsingular, the only solution would be "all digits zero", which contradicts the problem statement.) However, this is a constrained problem, in which all solution variables are unique integers between 1 and 9, inclusive. It turns out that there is only one valid solution, among the possible Perm(9,5) = 15,120 selections. There are a couple of other ways to solve this problem directly. Notice that even though there are an infinite number of solutions, all of them are scalar multiples of one another, so in a certain sense, there is only one solution. If we find one, we have found them all, to within a scalar multiplicative factor. Using an HP48G/49G/50G and assuming the system matrix is stored in a variable A, do this: Type A EGV to get the eigenvectors and eigenvalues. Examine the eigenvalues which are in a vector on stack level 1; one of them will be nearly zero. In this case, they are complex, but on my HP50, the 4th one is (1.005646484E-13,0), close enough to zero. This tells us we want the 4th eigenvector, which is in a matrix on stack level 2. Drop the vector on level 1 and enter the matrix editor to delete all the columns except the 4th. Exit the matrix editor and see on the stack: [[ (.25, 0. ) ] [ (.125, 0. ) ] [ (.375, 0. ) ] [ ( 1. , 0. ) ] [ (.875, 0. ) ]] The imaginary parts are zero, so convert it to real. This is one of the solutions to the problem, but we want an all integer solution. It looks like if we multiply by 8 we will get what we want, [ 2 1 3 8 7 ]T. If we form ATA first, we will get real eigenvectors and eigenvalues, with the same solution. Another method is this: Type A SVD DROP SWAP DROP TRN to get only the transpose of the V matrix on the stack. Enter the matrix editor and delete all but the last column. Exit the matrix editor and see on the stack: [[ .177471301883 ] [ 8.87356509416E-2 ] [ .266206952825 ] [ .709885207533 ] [ .621149556591 ]] This is again one of the infinite solutions; it is the solution of length 1. Now we need to convert to integers. I would start by dividing by the smallest element in the vector. Enter the matrix editor to extract the 2nd element; press NXT to get to the ->STK function. Exit the matrix editor with this number on the 2nd level of the stack and the vector still on level 1; press SWAP /. See: [[ 2 ] [ 1 ] [ 3 ] [ 8 ] [ 7 ]] We lucked out, and that one division gave us the integer solution we were looking for. All done, without knowing that the sum of the digits is 21.

 Eigenvalues and Singular-value decompositionMessage #4 Posted by Karl Schneider on 30 Jan 2008, 1:15 a.m.,in response to message #3 by Rodger Rosenbaum Rodger -- Very good! Using eigenvalue analysis and singular-value decomposition (SVD) to obtain the answers was enlightening. I, too, saw the connection to the eigenanalysis formulation, but knowing that the exact eigenvalue was zero, wasn't sure how much help it would be. It appears that the process of computation steered the eigenvector to the desired value. SVD was introduced to me in a graduate-level linear systems course 11 years ago. The instructor provided supplemental materials for the topic, because it wasn't covered in the text. As you indicated, these methods aren't available in the RPL-based HP-28 or the RPN-based calc's (of which only the HP-42S would have enough horsepower). Matlab, however, computed the correct eigenvalues (including zero) and normalized eigenvectors adroitly. Much of my point of that example was to show that such a calculation could be tackled using a quarter-century-old HP-15C. With its 64 allocatable storage locations, the following linear-algebra and matrix problems can be solved: Determinant and norms of an 8x8 real-valued matrix (64 registers) Solution of a 7th-order, real-valued, exactly-determined system with preservation of the constant vector (63 registers) or without preservation (56 registers) Closest solution of an overdetermined, inconsistent 5th order real-valued system in six equations, as I demonstrated (60 registers) Solution of a 4th-order, complex-valued, exactly-determined system by a special technique (64 registers) Solution of a 3rd-order, complex-valued, exactly-determined system by the standard method with preservation of the constant vector (48 registers) Quite impressive for the era, I'd say... -- KS Edited: 1 Feb 2008, 11:26 p.m. after one or more responses were posted

 Re: Eigenvalues and Singular-value decompositionMessage #5 Posted by Rodger Rosenbaum on 30 Jan 2008, 3:14 a.m.,in response to message #4 by Karl Schneider By the way, remember this from one of your posts? Quote:BTW, flag -54 was indeed clear (the default setting) on my HP-49G when I obtained the least-squares "LSQ" solution to your exactly-determined system with the singular (thus, rank-deficient) matrix: 2.01952510743 2.23362533599 1.20500296581 2.00465552820 This solution, when multiplied by your matrix A, produced your vector B with an error of one ULP on two elements, and was exact on the other two. I got a very different result from "LSQ" with flag -54 set: 673.501526294 -1004.98937644 -1677.5 1456.88232477 This solution, when multiplied by your matrix A, produced a residual from B of 10-10*[263 368 275 493]T. For that last one I get 10^-10*[223 368 235 753]T on the HP50G. I checked these on an HP48G and on my HP49G, and I got the same thing I get on the HP50G, not the slightly different results you get. Are you using an HP49G emulator, or a real calculator? My HP49G has version 1.05 firmware. I wonder what's causing the small differences.

 HP-49G versionMessage #6 Posted by Karl Schneider on 1 Feb 2008, 2:18 a.m.,in response to message #5 by Rodger Rosenbaum Quote: Are you using an HP49G emulator, or a real calculator? My HP49G has version 1.05 firmware. I'm using a real ACO blue HP-49G, puchased in 2002. A few years ago, I verified its ROM as the latest version available. "VER" gives 4.2000031 as the CAS version. "VERSION" (thanks, Giancarlo!) gives "Version HP-49C Revision #1.18" "Copyright HP 2000" -- KS Edited: 1 Feb 2008, 3:00 a.m. after one or more responses were posted

 Re: HP-49G versionMessage #7 Posted by Giancarlo (Italy) on 1 Feb 2008, 2:25 a.m.,in response to message #6 by Karl Schneider Hi Karl. Quote: ew years ago, I verified its ROM as the latest version available. "VER" gives 4.2000031 as the CAS version. Wasn't it just the "extended version" :) of the "VER" one, i.e. "VERSION"? Hope this helps. Best regards. Giancarlo

 Thanks, Giancarlo! (HP-49G version)Message #8 Posted by Karl Schneider on 1 Feb 2008, 3:02 a.m.,in response to message #7 by Giancarlo (Italy) Hi, Giancarlo -- Thanks! I have updated my post. My HP-49G is newer than Rodger's. -- KS

 Re: Thanks, Giancarlo! (HP-49G version)Message #9 Posted by Giancarlo (Italy) on 1 Feb 2008, 3:46 a.m.,in response to message #8 by Karl Schneider Hi Karl. You're welcome, even though I realize that my quoting from your post was quite meaningless (my fault for not carefully checking which part of the post I selected and what was pasted in my reply...) However, glad I could be of some help :) Best regards. Giancarlo

 Re: "Ask Marilyn!" (Rank-deficient matrices and the HP-15C)Message #10 Posted by Rodger Rosenbaum on 29 Jan 2008, 8:50 p.m.,in response to message #2 by Karl Schneider Quote:It is quite plausbile that the "least-squares" solution to the overdetermined system will be the valid solution, because its elements are all single-digit integers having low magnitudes. It's more than just plausible; it's a must. A "least-squares" solution to an overdetermined system can be exact. Since the LSQ command finds the solution with the least error, if there is a solution with zero error (an exact solution, in other words), the LSQ command will find it. Since we were given that there is an exact solution in integers, and your addition of the last row is another bit of exact information about the solution, the system will have only one "least squares" solution, one where the residual is not just minimized, but actually zero.

 Re: "Ask Marilyn!" (Rank-deficient matrices and the HP-15C)Message #11 Posted by Karl Schneider on 2 Feb 2008, 12:17 a.m.,in response to message #10 by Rodger Rosenbaum Hi, Rodger -- I stated: It is quite plausbile that the "least-squares" solution to the overdetermined system will be the valid solution, because its elements are all single-digit integers having low magnitudes. You stated: Quote: It's more than just plausible; it's a must. A "least-squares" solution to an overdetermined system can be exact. Since the LSQ command finds the solution with the least error, if there is a solution with zero error (an exact solution, in other words), the LSQ command will find it. My statement was made without any analysis of the the rank of the "augmented" system. An effectively-underdetermined system (rank-deficient matrix) would have an infinite number of solutions on a line, plane, or other space, so "LSQ" would return the one with minimum Euclidean/Frobenius norm (rms magnitude). Since the desired solution consisted of single-digit integers, it seemed a good bet that the desired solution would be returned in any case. The original 5-equation system had a rank of 4, according to Matlab. Now, recall that I had previously calculated only the matrix' zero determinant, not its rank -- what if that had been 3? In fact, I had only stated without proof that substituting the "sum of digits" equation for a given equation would allow the system to be solved directly. Adding the "sum of digits" equation increased the rank from 4 to 5. Augmenting that matrix by the "constants column" [0 0 0 0 0 21]T produced a 6x6 matrix still having a rank of 5, because the column was consistent with the matrix. So, the solution produced was the only one possible. Quote: Since we were given that there is an exact solution in integers, But that is not represented in the system of equations... Quote: and your addition of the last row is another bit of exact information about the solution, the system will have only one "least squares" solution, one where the residual is not just minimized, but actually zero. That is absolutely correct, but the computational exercise was still worthwhile, I think. -- KS Edited: 2 Feb 2008, 12:22 a.m.

 Rank-deficiency and "determination" Message #13 Posted by Karl Schneider on 2 Feb 2008, 5:52 p.m.,in response to message #12 by Rodger Rosenbaum Rodger -- Quote: The first sentence in this paragraph from the original "Marilyn" post seems to indicate that you had calculated its rank. (Karl:) A is singular, with a rank of 4. So, the set of all real-valued possible solutions lie on a line in five-dimensional space. Touche'! "So long is the thread, I forgot what I said." In actuality, my "rank of 4" statement was only an educated guess that turned out to be true, after subsequent verification by Matlab. Quote: What you say about what if the rank of the original matrix had been 3 is quite true, but it wasn't, and you knew it and so did I. Please see above. :-) Quote: Golub and Van Loan put it succinctly: "When there are more equations than unknowns, we say that the system Ax = b is overdetermined." "We say that a system Ax = b is underdetermined whenever m < n." (m is the number of rows in the A matrix and n is the number of columns.) The HP48G User's Manual doesn't say it explicitly, but what they do say on page 14-14 could be interpreted to mean that a system with more equations than unknowns might be, in a sense, considered to be underdetermined under some conditions. These questions of terminology and definitions have convinced me to find and purchase another text on linear algebra and matrices, so that another reference with alternative explanations and discussions will be readily available to me. My sophomore-level text gives scanty treatment to the "determination" of linear systems, and my Google search for directly-useful on-line material was not particularly rewarding. -- KS Edited: 2 Feb 2008, 6:03 p.m.

 Re: Rank-deficiency and "determination" Message #14 Posted by Rodger Rosenbaum on 2 Feb 2008, 8:12 p.m.,in response to message #13 by Karl Schneider I would highly recommend "Matrix Computations" by Gene Golub and Charles Van Loan. It's not a textbook, but it's in its 3rd edition and it's the modern bible when it comes to how anything is done involving matrix computations. It's also a paperback and an incredible bargain at about \$40. For a text, my favorite is "Linear Algebra and Its Applications", by Gilbert Strang. It's also a modern text, in it's 4th revision I think. It isn't a high powered graduate level text, but it's modern and deals with the orthogonal decompositions that have become so important nowadays, with a very readable style. Go back to the main exhibit hall