test problem non-square inversion

Test Problem PhL 3.3.16 This doc gets filed under "inverse of non-square matrices". It is the simplest example I can think of that has content. My lack of knowledge on non-square matrices is simply breathtaking, considering I have spent a whole life dealing with matrices. My whole fat matrix binder is only square matrices. 1. The Setup Consider this equation SR = 1 which involves S being a 2 x 3 matrix and R being a 3 x 2 matrix: = This matrix equation is really a set of 4 equations as follows: S11R11 + S12R21 + S13R31 = 1 S21R11 + S22R21 + S23R31 = 0 S11R12 + S12R22 + S13R32 = 0 S21R12 + S22R22 + S23R32 = 1 Suppose we are given matrix R and we want to find a solution matrix S that causes SR = 1. [ I know that at least one such S exists if R is full rank, from theorem below.] At first blush, you say "Well, there are 4 equations in 6 unknowns Sij, so the problem seems to be underconstrained and therefore likely has many solutions. There seem to be two (maybe continuous) degrees of freedom in the solution. " Now we do a very simple example. Suppose the given R matrix is Rij = 0 for all 6 elements. Then you can see that no choice of Sij can satisfy the first equation, so in fact there are in this case NO solutions! So the above vague argument in quotes is no good. I know from Shilov this fact (which I have not proven and neither does he directly) So my R matrix is m x n = 3 x 2 and the theorem says a left inverse S exists only if rank(R) = 2. So this theorem is compatible with my simple example where rank(R) = 0. As I find far below, in general neither of these inverses is unique, but there is a nice formula for finding a candidate left or right inverse given that the matrix A is full rank. So I want to know WHY one needs to have rank(R) = 2 in order to have a solution. And I then want also to know how many solutions there might be in that case. I am off to a good start in that I know several facts about "rank". If I can explain this simple example, then maybe I can explain the theorem quoted above. 1. Plan A. Suppose you knew the solution values for S13 and S31. Look at the first two equations: S11R11 + S12R21 + S13R31 = 1 S21R11 + S22R21 + S23R31 = 0 which rewrite then as S11R11 + S12R21 = - S13R31 + 1 S21R11 + S22R21 = - S23R31 a x + b y = A c x + d y = B If I solve for x = R11 and y = R21, I could say that must have a certain 2x2 det vanish. But I am NOT in this problem solving for these unknowns because the Rij are given. Suppose we change the problem to accommodate Plan A. Suppose we are given the Sij and we want to find the Rij. So we are looking then for a right inverse of S. So we are given the Sij and suppose we assume that we magically know the solution value for R31. Then the x and y shown above really are unknowns. and to solve this pair of equations you must have det ≠ 0 Since matrix S then has a non-vanishing 2x2 minor, it must be rank 2. So for this second problem I have answered the question of why S must be full rank. Now look instead at the first and third equations and go back to the first problem: S11R11 + S12R21 + S13R31 = 1 S11R12 + S12R22 + S13R32 = 0 We know the Rij and we want to find the Sij. Suppose we know S13 somehow. Then write as S11R11 + S12R21 = - S13R31 + 1 S11R12 + S12R22 = - S13R32 or R11S11 + R21S12 = - S13R31 + 1 R12S11 + R22S12 = - S13R32 or a x + b y = A c x + d y = B NOW the unknowns are S11 and S12 and for this pair to have a solution we must have det ≠ 0 Thus R must have full rank 2, so we have done it now in both directions. I have verified the theorem. 2. Can I generalize this idea somehow! Here again are the equations for our simple example: S11R11 + S12R21 + S13R31 = 1 S21R11 + S22R21 + S23R31 = 0 S11R12 + S12R22 + S13R32 = 0 S21R12 + S22R22 + S23R32 = 1 which can be written (here summation index 3 is really m, the number of rows in R which is m x n) Σi=13 S1iRi1 = 1 Σi=13 S2iRi1 = 0 leftmost column of unity matrix Σi=13 S1iRi2 = 0 Σi=13 S2iRi1 = 1 rightmost column of unity matrix I think the generalization for R which is m x n is this: Σi=1m S1iRi1 = 1 Σi=1m S2iRi1 = 0 Σi=1m S3iRi1 = 0 ... Σi=1m SniRi1 = 0 n equations Σi=1m S1iRi2 = 0 Σi=1m S2iRi2 = 1 Σi=1m S3iRi2 = 0 ... Σi=1m SniRi2 = 0 n equations Σi=1m S1iRin = 0 Σi=1m S2iRin = 0 Σi=1m S3iRin = 0 ... Σi=1m SniRin = 1 n equations In each group there are in fact n equations, so there are the famous n2 equations in m*n unknowns. Look now at the second problem where we want to know the Rij given the Sij. In this case consider just the first set of n equations. Write them as Σi=1n S1iRi1 + Σi=n+1m S1iRi1 = 1 Σi=1n S2iRi1 + Σi=n+1m S2iRi1 = 1 Σi=1n S3iRi1 + Σi=n+1m S3iRi1 = 1 ... Σi=1n SniRi1 + Σi=n+1m SniRi1 = 1 Now suppose that we know not only the Sij but we know the "higher Rij" values in those second sums. Then rewrite as Σi=1n S1iRi1 = 1 - Σi=n+1m S1iRi1 Σi=1n S2iRi1 = 1 - Σi=n+1m S2iRi1 Σi=1n S3iRi1 = 1 - Σi=n+1m S3iRi1 ... Σi=1n SniRi1 = 1- Σi=n+1m SniRi1 where everything on the RHS's is constant and known. Think of the Rij as your n unknowns and the Sij as coefficients. We then have a Cramer's problem with n equations in n unknowns. In order for there to be a solution, we must have det(Sij) ≠ 0 for this n x n submatrix Sji where i = 1..n and j = 1..n . This is the leftmost n x n minor in matrix S. But this is the max size minor inside S, and this S must be rank n, QED. For the "other" problem If I were to take the first equation in each group above Σi=1m S1iRi1 = 1 Σi=1m S1iRi2 = 0 ... Σi=1m S1iRin = 0 then I make the mirror argument and show that if the Rij are known, need rank R = n. Now suppose we had instead taken the second grouping, Σi=1m S1iRi2 = 0 Σi=1m S2iRi2 = 1 Σi=1m S3iRi2 = 0 ... Σi=1m SniRi2 = 0 n equations and suppose we write this as Σi=1n S1iRi2 = 1 - Σi=n+1m S1iRi2 Σi=1n S2iRi2 = 1 - Σi=n+1m S2iRi2 Σi=1n S3iRi2 = 1 - Σi=n+1m S3iRi2 ... Σi=1n SniRi2 = 1- Σi=n+1m SniRi2 We still have a Cramer's rule problem but the unknowns are now Ri2 instead of Ri1. The Sij coefficients are the same as in the previous analysis, so we conclude that det(Sij) ≠ 0 again for the leftmost minor in S. So all equation groups would result in this same minor being non-zero. I get the impression that by shuffling the equations around I could show that ANY nxn minor of S must be non-zero. That then seems like overkill since for a rank n matrix S, you might have only one of the n x n minors being zero. So something is missing. If in the above equation set all the RHS objects were 0, then you could not conclude that det ≠ 0 because there is a Cramer 0/0 situation. Suppose this happened in the last case above, so our equations became, Σi=1n S1iRi2 = 0 Σi=1n S2iRi2 = 0 Σi=1n S3iRi2 = 0 ... Σi=1n SniRi2 = 0 Would write this as vector equation Σi=1n SiRi2 = 0 Si = column of S's shown = column i This would say that the columns of Sij were linearly dependent, but we already know that. But maybe some variation on this could work. I won't try to complete my proof today. But here is the main thing learned: Fact: If you have n2 equations in n*m unknowns, you can NOT conclude that since n < m you have a whole continuum of solutions because you are underconstrained. The fact is that you have no solutions whatsoever unless the known matrix is full rank. Combined with the "other way" below, I have shown that for either "problem" the known matrix (R or S) must be full rank because it has a max size minor, barring the possibility of all the RHS quantities happening to be 0. My proof was based on Cramer's rule and finding subproblems that were n x n. I saw trivial counterexamples. Question: Assuming maximum rank, are the inverses unique? Someone gives this formula, (wiki page on "inverse element". So look at this again. ATA is a square matrix I think. So you see how this plays out. The case above applies to the SR = 1 case. You can see how it works graphically. You will needed det(ATA) ≠ 0, and this seems related to Sjamaar's page where this object appears. But not clear whether the above inverses are unique or not. One PDF said the inverses above are the nicest ones, but are not the only ones! So not unique! Fact: The inverses of non-square matrices are NOT unique. Here are some examples from a pdf: More interesting items: Does this mean there is at most one solution for each inverse X ? I think so. I don't get it. Seems the same as my answer to the previous case. Another hit "In general, left inverses are not unique. " "In general, right inverses are not unique." Conclusions: 1. For an appropriately shaped matrix, a left or right inverse exists if the matrix is full rank. 2. In general the left or right matrices are not unique. 3. You can always write one such left or right inverse using the formulas shown above. 4. Nobody is saying how many left or right inverses might exist. I found a weird pdf that at least tries to answer this question, but the answer is a bit complicated ijsr.net/archive/v4i9/SUB156717.pdf