Re: Transpose

*To*: mathgroup at smc.vnet.net*Subject*: [mg5783] Re: Transpose*From*: Robert Villegas <villegas>*Date*: Sat, 18 Jan 1997 14:58:36 -0500*Sender*: owner-wri-mathgroup at wolfram.com

> Transpose[list] transposes the first two levels in list. Transpose[list, {n1, > n2, ...}] transposes list so that the nk-th level in list is the k-th level > in the result. > > Now suppos matrix is a square matrix. Why gives Transpose[matrix,{1,1}] the > diagonal? This was asked a couple different times over a year ago, and Allan Hayes and I, among others, tried to answer this. Although I never found an explanation I was really happy with, here are a couple different attempts I made that at least cover the issues (I made some changes to number 2 from the original). ========================================================================= Explanation 1 ========================================================================= Usually Transpose is used to permute levels. Here is a little trick using the humble Table command to help understand what Transpose is doing. Suppose you have an m x n x p matrix (3 dimensions), and you do Transpose[m, {3, 1, 2}] This is equivalent to a Table command that rearranges levels manually: Table[m[[ i3, i1, i2 ]], {i1, n}, {i2, p}, {i3, m}] The order of the indices inside of m -- i3, i1, i2 -- corresponds to the order of the integers that Transpose takes: 3, 1, 2. Now it's easier to see why Transpose behaves the way it does if the integers aren't all distinct. Suppose I did Transpose[m, {2, 1, 2}] If I follow the rule in the last example, then I will form a Table of m[[ i2, i1, i2 ]], where now there are only two indices, and the second one, i2, appears in both the first and third slots of m. That means slots 1 and 3 of m vary together, not independently! For any value if i1, say 5, we'll run i2 through all its values and get a list of entries: m[[1, 5, 1]], m[[2, 5, 2]], m[[3, 5, 3]], ... and so on ... When two (or more) indices vary together, you form a diagonal out of those dimensions. In Roman's function, the matrix is two dimensional, so Transpose[m, {1, 1}] forms the familiar diagonal, a vector. Here is a little illustration on a 3D matrix. We plan to form a diagonal out of dimensions 1 and 3, so we'll mark the entries of the original matrix which have 1st and 3rd indices equal. In[46]:= m = Array[SequenceForm, {2, 3, 2}]; MatrixForm[m] Out[46]//MatrixForm= 111 121 131 112 122 132 211 221 231 212 222 232 In[47]:= tagEntry[entry_, test_] := If[test, SequenceForm["*", entry, "*"], SequenceForm[" ", entry, " "]] If the position of an entry has 1st and 3rd indices equal, we surround it with asterisks: In[49]:= MapIndexed[tagEntry[#1, #2[[1]] == #2[[3]] ]&, m, {3}] //MatrixForm Out[49]//MatrixForm= *111* *121* *131* 112 122 132 211 221 231 *212* *222* *232* These are exactly the ones selected by specifying {1, 2, 1} in Transpose: In[50]:= Transpose[m, {1, 2, 1}] //MatrixForm Out[50]//MatrixForm= 111 121 131 212 222 232 With more dimensions, there is enough room to form a single diagonal out of three (or more) dimensions, collapsing several dimensions down to one. You can also take more than one set of dimensions and collapse them, forming several diagonals. For instance Transpose[m, {1, 2, 2, 1, 1}] would vary slots 1, 4, and 5 together, forming a diagonal. Independent from that diagonal, slots 2 and 3 would vary together, forming another diagonal. You would get a product of two diagonals, and the result would have 2 dimensions. Important: the dimensions being combined into a diagonal have to have the same length, else their indices can't vary together (one index can go past the point where the other is defined). Thus, you can't take the diagonal of a non-square matrix, such as a 3 x 5: In[45]:= Transpose[Array[SequenceForm, {3, 5}], {1, 1}] Transpose::perm: {1, 1} is not a permutation. Out[45]= Transpose[{{11, 12, 13, 14, 15}, {21, 22, 23, 24, 25}, > {31, 32, 33, 34, 35}}, {1, 1}] Actually, you could define a diagonal by varying the indices only up to the smallest ceiling among all of them. The last time someone asked about this use of Transpose, Allan Hayes wrote a generalization of Transpose to do it. ========================================================================= Explanation 2 ========================================================================= Regarding the two-argument form of Transpose U = Transpose[T, {p1, p2, ..., pn}] where T is an n-dimensional tensor (i.e. TensorRank[T] == n). It is true that {p1, p2, ..., pn} is a permutation of the levels of T. This permutation says that level 1 in T becomes level p1 in U; level 2 in T becomes level p2 in U; . . . ; and level n in T becomes level pn in U. As a mapping, you could write this as {1 -> p1, 2 -> p2, . . . , n -> pn} That's fairly simple to state, but awfully abstract, and I had to look at a bunch of examples to make sense of it, so let's look at one. Let's say the permutation is {3, 1, 2}. So the change of levels, or the change of indices, is {1 -> 3, 2 -> 1, 3 -> 2} What this means is: if you pick an object in T whose indices are (5,8,7), then the same object in U will be found at (8,7,5). Index 1 moved to index 3, index 2 moved to index 1, and index 3 moved to index 2. U(8,7,5) = T(5,8,7) Let's try out this method on a 3D array all of whose entries are distinct, so we can tell where each entry has moved. In[16]:= t = Array[SequenceForm, {2, 3, 4}] Out[16]= {{{111, 112, 113, 114}, {121, 122, 123, 124}, {131, 132, 133, 134}}, > {{211, 212, 213, 214}, {221, 222, 223, 224}, {231, 232, 233, 234}}} In[17]:= u = Transpose[t, {3, 1, 2}] Out[17]= {{{111, 211}, {112, 212}, {113, 213}, {114, 214}}, > {{121, 221}, {122, 222}, {123, 223}, {124, 224}}, > {{131, 231}, {132, 232}, {133, 233}, {134, 234}}} For instance, ask where t's (1,2,3) entry went. Our permutation argument {3, 1, 2} says to move 1st to 3rd, 2nd to 1st, and 3rd to 2nd. This gives new indices of (2,3,1). Let's check this: In[18]:= Part[t, 1, 2, 3] Out[18]= 123 In[19]:= Part[u, 2, 3, 1] Out[19]= 123 A Mathematica expression that expresses the index-moving rule is as follows: Tcoords = Part[Ucoords, {p1, p2, ..., pn}] Regarding the example on p. 100 of _Programming in Mathematica_, 2nd edition, by Roman Maeder: Maeder says that when the p's in your level re-arrangement {p1, p2, ..., pn} are not distinct, then Transpose takes the diagonal. Recall that the pi's give you the destination levels of the original levels. If I have a 3D array and I specify {1, 1, 1}, then I'm moving all indices in the original array to the first index in the new array. It doesn't seem sensible to have the three different indices (i,j,k) in the original array become one in the new array. But if i = j = k, it is possible: (i,j,k) becomes (i). So Transpose[T, {1, 1, 1}] can be defined as the one-dimensional array of T entries (i,j,k) which have the property i = j = k. That is nothing more than the diagonal of a matrix! Here's a 3 x 3 x 3 that collapses to a 3-element vector under the {1, 1, 1} transpose operation: In[22]:= m3 = Array[SequenceForm, {3, 3, 3}] Out[22]= {{{111, 112, 113}, {121, 122, 123}, {131, 132, 133}}, > {{211, 212, 213}, {221, 222, 223}, {231, 232, 233}}, > {{311, 312, 313}, {321, 322, 323}, {331, 332, 333}}} In[23]:= Transpose[m3, {1, 1, 1}] Out[23]= {111, 222, 333} It's possible to merge some levels, but not others. For instance, Transpose[m3, {1, 2, 1}] will merge levels one and three. In[24]:= Transpose[m3, {1, 2, 1}] Out[24]= {{111, 121, 131}, {212, 222, 232}, {313, 323, 333}} Take a close look at the entries, and you'll see that the 1st and 3rd indices are always equal, where the 2nd index varies independently of them. Merging levels of the original array means that those indices will vary together, so those lengths of those dimensions must be equal (if they aren't equal, then one index can take on values that the other one cannot). Because non-distinct pi's in Transpose[T, {p1, p2, ..., pn}] means two or more dimensions will collapse to one, the resulting array necessarily has fewer dimensions than the original. If I collapse a 3D array this way, then I can't specify a destination level of 3 in my permutation, because there will be fewer than 3 dimensions in the result: In[17]:= Transpose[m3, {1, 3, 1}] Transpose::newdims: Level rearrangement {1, 3, 1} does not specify destination for level 2. Out[17]= Transpose[{{{111, 112, 113}, {121, 122, 123}, {131, 132, 133}}, {{211, 212, 213}, {221, 222, 223}, {231, 232, 233}}, {{311, 312, 313}, {321, 322, 323}, {331, 332, 333}}}, {1, 3, 1}] *Rule* If I give a "permutation" {p1, p2, ..., pk} that has exactly r distinct integers in it, then they must all be <= r. Here's an example of collapsing a 5-tensor to a 2-tensor by taking the diagonal in dimensions 1, 3, and 5, and another diagonal in dimensions 2 and 4: In[37]:= Transpose[Array[SequenceForm, {3, 3, 3, 3, 3}], {1, 2, 1, 2, 1}] Out[37]= {{11111, 12121, 13131}, {21212, 22222, 23232}, {31313, 32323, 33333}} Indices 1, 3, and 5 change as you move across level 1, whereas indices 2 and 4 change as you move across level 2 (the elements of the sublists). To recap two caveats regarding non-distinct pi: (1) If you map two levels to the same level, they must have the same length, otherwise you can't take their diagonal (well, I think there are pseudo diagonals or something for rectangular matrices, but the code doesn't allow that). (2) If you have only r distinct destination levels, then all destination levels must be <= r. Robby Villegas