Subdeterminants of a matrix

Subdeterminants of a matrix A PhL 3.28.09 An Example and a Notation used to describe a subdeterminant of matrix A We start with a simple example We start with a matrix, cross out some rows and columns, and this results in a smaller matrix which we show on the right, and our "subdeterminant" is the determinant of that "submatrix". The matrix on the right we call the auxiliary matrix. Our matrix in general is N x N, the submatrix is n x n. We propose the following notation and formula for the subdeterminant discussed above: det124;134 = Σi1,i2,i3 {134} A1,i1 A2,i2 A4,i3 εi1 i2 i3 ε134 = 1 There are some subtleties in this notation that need to be brought out: The Meaning of ε Normally we talk about a totally antisymmetric ε tensor εijk where i,j,k take values 1,2,3 and where ε123 = 1. The ε object we show in the above expression is essentially this same ε tensor, the only difference is that we have "translated" the set of indices from the canonical values {1,2,3} to the operational values {1,3,4}. This operational set is the set of columns of the original matrix A from which the submatrix is extracted. The numbers in this set will become the second indices on the Aa,b factors appearing above. In the translated index world, it is ε134 = 1 in place of the usual ε123 = 1. The columns of the auxiliary matrix have the canonical index values 1,2,3..., whereas the columns of the original matrix have the operational values, and these are always the ones we care about. The notation detrows;cols We are going to talk in a moment about a notation detrows;cols where rows = a set of rows from the original matrix that will contribute to a subdeterminant, and cols = a set of cols from the original matrix that will contribute to a subdeterminant. In our example above, rows = 124 and cols = 134. Notice for example that rows = all rows - those rows crossed out cols = all columns - those columns crossed out Natural Order When a set of numbers is in monotonic increasing order, we refer to that as a "natural order". In our example above, we have det124;134 . Each of the two sets rows and cols is in natural order. This will always be the case if we talk about an "in situ" submatrix as a piece of matrix A. We imagine that we form the "auxiliary matrix" shown on the right above by "translating" the 9 selected elements from the full A matrix and plop them without any ordering rearrangement into the auxiliary matrix. Arbitrary 3x3 subdeterminant of A We can now write a formula for an arbitrary 3x3 matrix of our original 4x4 matrix above: detr1 r2 r3; c1 c2 c3 = Σi1,i2,i3 {c1 c2 c3} Ar1,i1 Ar2,i2 Ar3,i3 εi1 i2 i3 with εc1 c2 c3 = 1. For this formula to be correct, we insist that both the sets called rows and cols be in natural order. As noted above, this means that r1 < r2 < r3; and c1 < c2 < c3; The "leading term" in the above formula for detr1 r2 r3; c1 c2 c3 is this: + Ar1,c1 Ar2,c2 Ar3,c3 which corresponds to the term with i1 = c1, i2 = c2 and i3 = c3 and uses εc1 c2 c3 = 1. Remember, this is just the "translated" version of the canonical ε123= 1. What happens to the elements of the rows and cols groups? We now want to reinforce in the reader's mind where the numbers in the two groups "rows" and "cols" go: detrows;cols = detr1 r2 r3; c1 c2 c3 = Σi1,i2,i3 {c1 c2 c3} Ar1,i1 Ar2,i2 Ar3,i3 εi1 i2 i3 Above we show in red the elements of the rows group. The numbers in this group appear as the first indices on the A factors, and they appear there exactly in the order they appear in the rows group. Remember that in the notation Aab the first index is the row index, telling you in which row of the matrix A this matrix element lies. detrows;cols = detr1 r2 r3; c1 c2 c3 = Σi1,i2,i3 {c1 c2 c3} Ar1,i1 Ar2,i2 Ar3,i3 εi1 i2 i3 Above we show the cols group elements in red. These elements are the "legal values" of the summation indices. As the sum is written out, it is these values which will become in various permuted orders the second index of the various Aab factors. This second index is the column index. Let's write out two terms: detr1 r2 r3; c1 c2 c3 = Ar1,c1 Ar2,c2 Ar3,c3 – Ar1,c1 Ar2,c3 Ar3,c2 + 4 other terms Recall our translated convention that εc1 c2 c3 = +1 . This is why the first term above has a plus sign. The second term is really + εc1 c3 c2 Ar1,c1 Ar2,c3 Ar3,c2 but we know that when we swap any two indices on the totally antisymmetric ε tensor we must get a minus sign, so εc1 c3 c2 = -1. Note Added: Were we to use the "transpose ε formula" it might be more obvious that cols form the column indices. We are generally avoiding these transposed formula versions, but this seems a good place to use one: detrows;cols = detr1 r2 r3; c1 c2 c3 = Σi1,i2,i3 {r1 r2 r3} Ai1,c1 Ai2,c2 Ai3,c3 εi1 i2 i3 In general you hold one set of indices fixed and permute the other set, and there are two ways to do this. Arbitrary n x n subdeterminant of A Let's now generalize the above result for an n x n subdeterminant instead of a 3 x 3 one: detrows;cols = detr1 r2..rn; c1 c2..cn = Σi1,i2,..in {c1 c2 ..cn} Ar1,i1 Ar2,i2 Ar3,i3...Arn,in εi1 i2 ..in with εc1 c2 ..cn = 1 and rows,cols both assumed to be in natural order The reader should hopefully feel fairly comfortable with the above result. It is basically just a restatement of the basic ε determinant formula in its "rows fixed" mode, but where we have "translated" the indices in this way: row: 123...n → r1r2..rn and col: 123...n → c1c2.cn . We then have to understand the ε symbol in terms of its translated index set, which is not so difficult to do. Groups potentially in unnatural order (indicated here by primes) As noted earlier, we have in mind in all the formulas quoted so far that rows and cols have elements which are in "natural" order, monotonic increasing. We now want to generalize our notation to allow for rows and cols to be NOT in natural order. Consider rows' = c2 c1 c3 = a permutation of the natural order c1 c2 c3 obtained by doing 1 swap We know that we can get from any order to the natural order by doing a certain number of pairwise index swaps, one in the above example. So imagine that for some general rows' we have rows' = some permutation of rows with R swaps required to make rows'→ rows cols' = some permutation of cols with C swaps required to make cols'→ cols Now, consider again our determinant det124;134 presented at the very beginning above. Both the rows and cols sets are in natural order. We would then mean by det214;134 the determinant of the 3 x 3 matrix where we swap rows 1 and 2. That is, we swap these two rows of the original matrix A to get this new 3x3 auxiliary matrix which has this new determinant. But we know that swapping any pair of rows (or pair of columns) of a matrix changes the sign of the determinant. Thus, we know that det214;134 = – det124; 134 = (-1)1 det124; 134 It should be pretty clear that the general idea for dealing with rows and cols in non-natural order is this: detrows';cols' = (-1)R+C detrows;cols where R+C is the total number of row + column index swaps that are required to change rows' → rows and cols' → cols. We can then use the above formula for detrows;cols which applies for naturally order rows and cols groups. The groups called rows and cols are ordered sets. We now want to reinforce the idea that the groups or sets like rows, rows', cols, cols' which have been discussed above are "ordered sets". The ordering matters, so they are not just "regular sets". Recall our highlighted results above: detrows;cols = detr1 r2 r3; c1 c2 c3 = Σi1,i2,i3 {c1 c2 c3} Ar1,i1 Ar2,i2 Ar3,i3 εi1 i2 i3 detrows;cols = detr1 r2 r3; c1 c2 c3 = Σi1,i2,i3 {c1 c2 c3} Ar1,i1 Ar2,i2 Ar3,i3 εi1 i2 i3 In the first, we see how the ordering of "rows" matters, because the ordered elements of "rows" are going to be attached as the first indices of the Aab factors, and order does matter here because if you do things in the wrong order, you might get a minus sign. For example, if you wrote Ar2,i1 Ar1,i2 then you would rewrite that as Ar1,i2 Ar2,i1 and you would correct for that by renaming the dummy indices i1↔i2, but then to get these indices back in the right place in the ε you have to swap two indices and this makes a minus sign. The fact that ordering matters for "cols" is slightly less obvious. Cols is just a "regular" set in the sense of Σi1,i2,i3 {c1 c2 c3}, but where it matters is in the ancillary statement that εc1 c2 c3 = +1 . Again, if we put things in the wrong order, we might get a minus sign error. [ Again, the columns situation can be understood using the transpose form.] Summary of results for arbitrary subdeterminants of the matrix A An arbitrary subdeterminant of a matrix A (including allowing for shuffles of rows and/or columns) can be described by this notation detrows'; cols' where rows' and cols' might not be in natural order (which would be the case if there were some row and or column permutations.) But we know that we can get back to both groups being in natural order by saying detrows';cols' = (-1)R+C detrows;cols where R+C is the total number of row + column index swaps that were required to change rows' → rows and cols' → cols. Once we are in natural order, we can then use our general natural order subdeterminant formula: detrows;cols = detr1 r2..rn; c1 c2..cn = Σi1,i2,..in {c1 c2 ..cn} Ar1,i1 Ar2,i2 Ar3,i3...Arn,in εi1 i2 ..in with εc1 c2 ..cn = 1 As simple examples, we know that det214;134 = – det124;134 R = 1 C = 0 det124;134 = Σi1,i2,i3 {134} A1,i1 A2,i2 A4,i3 εi1 i2 i3 with ε134 = 1 = A1,1 A2,3 A4,4 – A1,1 A2,4 A4,3 + A1,4 A2,1 A4,3 + 3 more terms ε134 = +1 ε143 = -1 ε413 = +1 where we highlight in red the two column indices we are going to swap to get the next term to the right. These swaps make minus signs because they are swaps of a pair of indices on ε as shown. One reason we might have to deal with detrows'; cols' with non-natural ordered groups is that these tend to occur in the free-ranging sums which appear, for example, in the Fredholm determinant and first minor, about which we shall have a lot to say later on. Definition of and Notation for a special case: diagonal subdeterminants In our analysis of the Fredholm Determinant, all subdeterminants involved will have the following property: rows' = cols' . I refer to a subdeterminant with rows' = cols' as being a "diagonal subdeterminant". I use this term because the diagonal elements of the auxiliary n x n matrix all come from the diagonal of the original matrix A. You get such a diagonal subdeterminant by crossing out the same set of rows and columns. Notice this property for diagonal subdeterminants when we take things to natural order: detrows';cols' = detrows';rows' = (-1)R+R detrows;rows = detrows;rows //diag subdet so there is no possible minus sign to worry about when we put the rows' and cols' groups both in natural order. We would then use the formula given above for natural order groups. Here is a shorthand notation I will use for a diagonal subdeterminant: detrows' ≡ detrows';cols' // for a diagonal subdeterminant Since the two groups are the same, we can save space by not replicating them. Our formula for a diagonal subdeterminant from above is now detrows ≡ detr1 r2..rn ≡ detr1 r2..rn; r1 r2..rn // natural order assumed = Σi1,i2,..in {r1 r2 ..rn} Ar1,i1 Ar2,i2 Ar3,i3...Arn,in εi1 i2 ..in with εr1 r2 ..rn = 1 Comment on Alternative formulas We have all along been using this formula for the determinant detA = εijk..A1iA2jA3k.... We could have used the different but equivalent "transpose formula" detA = εijk..Ai1Aj2Ak3.... which just reminds us that detA = detAT. This different formula would give us variations of our results above. Those variations involve replacing Aab with Aba everywhere. Knowing we could do it, let's not do it.