Taking the Transpose

The 15-Puzzle

2010-11-29T18:17:00.001-08:00

Is it possible to take a standard 15 puzzle (the numbers 1-15 on those sliding tiles, with one blank space) in the starting position:

1234

5678

9ABC

DEF_

and (without taking the pieces out of the puzzle) transpose the pieces so that the puzzle reads

159D

26AE

37BF

48C_

? It it possible to transpose the 3x3 8-piece puzzle in this way?

I know the answer... leave your thoughts in the comments.

O(1) Space Algorithm For Transposition

2010-11-03T05:05:00.000-07:00

The cheapest way to transpose a matrix in a computer is to simply change the labelling of the locations. To understand this, first we should understand how a generic way computer stores a vector and a matrix.

Suppose we had a column vector with n entries, and the computer stores the entries in memory slots 67 to 67+n-1. Then, when you ask the computer for the ith entry, it does not go to memory slot 67 and count i slots, it simply goes to slot 67+i (assuming 0-indexing) directly. This is different from how you or I do it when looking at a vector written on a page---we have to count some number of slots from the beginning (or end!) to get to the entry we want.

Suppose we had a matrix with n rows and m columns and the computer stores the entries in memory slots 85 to 85+mn-1. Then the canonical thing to do is to store the matrix in row-major order, which means storing the first row and then the second row and then the third, etc. Then, when you ask the computer for the (row,column)=(i,j)th entry, it does not count in two dimensions in a grid like you or I (the memory doesn't even know the data is laid out in a grid). Instead, it just goes to slot 85+im+j.

Suppose you want to transpose the above matrix. The fastest way is not to actually move any of the entries. Instead, the fastest way is to change the algorithm for accessing them. It is easy to see that if you want the (i,j)th entry of the transposed matrix, you should simply look at entry 85+jn+i---we have simply switched the role of rows and columns in the addressing system.

This is quite handy. But it's not always the best thing to do. There are a number of tasks where you need a whole row. Suppose you need the ith row. Then just go to memory slot 85+im, the first entry in the row, and read until you get to 85+(i+1)m-1, the last entry in the same row. Reading these entries is fast because they're all in order. But if you need a whole column, you have to jump around the memory quite a bit because the entries of a single column are sprinkled evenly throughout the memory, and that is quite slow. SO, if you're going to need to access whole columns frequently and whole rows infrequently, you're better off moving the entries around so that the columns are stored contiguously. Thus, we need to come up with an algorithm for transposing a matrix in memory.

Suppose you had a matrix that took up more than half your memory (for example, you're google and you're trying to diagonalize the PageRank matrix, which is so big you have to store it on multiple computers). Then you can't just make a copy in a different order because you wouldn't have enough room to write it down. Suppose you've used up 99.999% of your memory and yet you want to transpose a matrix. Is it possible to do so without needing more space than the matrix actually occupies (plus just two ((for example)) entries worth of scratch space)? This question is usually phrased as: "is it possible to transpose a matrix in place?" or "is it possible to transpose a matrix in O(1) space?" The problem is this: every time you want to write a value in a memory slot, if you don't store the entry currently stored there in your scratch space you fail: you will have overwritten a piece of the matrix that you cannot get back. So before writing anywhere, you'd better rescue the piece that you used to occupy that memory location. BUT, that dictates the next entry you need to move because you just don't have enough space to keep too many rescued pieces of information in memory. If you were moving something from memory slot 331 to 743, your next immediate step is to move the entry in 743 someplace else.

For square matrices, this is really easy, because the size of a row in memory at the beginning will be the same as the size of the row after transposition (because it is square, the columns have the same number of slots as the rows). So, if you were moving the entry at memory slot 331 to slot 743, then just move the entry from 743 to slot 331. Do this for a well-chosen half of the matrix (the upper triangle is a fine choice) and you will have accomplished the task.

However, it becomes significantly more complicated when the matrix is not square, because you can't just swap two entries. It's conceivable that every time you make an unforced move, that could force you to move many of the entries. Interestingly, Wikipedia has an article dedicated to the solution of this problem. The REALLY interesting part is that it is solved and the solution is nice.

The Pfaffian

2010-08-03T18:55:00.000-07:00

The Pfaffian has come up recently in a colleague's research. It happens equal to the square-root of the determinant (it is not defined this way, but in another way), but it is only defined on a 2n x 2n antisymmetric matrix. I began investigating it and I noticed this interesting property:

Of course, the determinant Det(A), which is the square of Pf(A), we know to be invariant under transpose, so that power of (-1)^n is quite fortunate! It will square away!

Also notice this: Taking the transpose of an antisymmetric matrix is equivalent to multiplying it by -1. That means that for some n Pf and -1 commute and for other n Pf and -1 anticommute! This may, therefore, be intimately tied to bosons and fermions!

IMPORTANT NEWS!

2009-09-14T20:01:00.001-07:00

"According to one of my professors, the transpose is equal to the conjugate transpose. This is a fundamental breakthrough in the science of transposes."

- Kyle Wardlow

Poetry

2009-05-24T15:19:00.000-07:00

The post contains no real content

2009-02-28T14:00:00.000-08:00

This post is mainly a reminder that we should continue to post awesome! jokes on this blog:

And now a terrible joke...

Q: What is the value of the contour integral around Western Europe?

A: Zero, because all the Poles are in Eastern Europe.

Symmetry of Lorentz Boost

2009-02-05T08:06:00.000-08:00

The Lorentz transformation matrix is symmetric under transpose!

Saving Lives with the Transpose

2009-01-08T12:56:00.000-08:00

While doing my usual transpose research, I stumbled upon this definition from the American Heritage Medical Dictionary:

transpose (redirected from "Transpose of a Matrix")

v. - to transfer one tissue, organ, or part to the place of another.

A natural extension of this is to write a matrix representation of the body, where each element in the matrix represents a location in the body. Then fill in the matrix with body parts, take the transpose, and that should tell you how to take the transpose of the human body. Try it out and let me know how it goes.

(Taken from: http://74.125.45.132/search?q=cache:ZLoWQTsWrK4J:medical-dictionary.thefreedictionary.com/Transpose%2Bof%2Ba%2Bmatrix+how+to+take+the+transpose+of+a+matrix&hl=en&ct=clnk&cd=10&gl=us&client=firefox-a)

Riddle: Transpose of Transpose

2008-12-17T18:05:00.000-08:00

Also note that the transpose contains 9 letters and thus may be written as a square matrix:

TRA

NSP

OSE

which could be transposed to give

TNO

RSS

APE

or, reading across, left-to-right and top-to-bottom,

"TNORSSAPE"

which is the cipher-text you would transmit if you performed a scytale encryption on the clear-text TRANSPOSE

http://en.wikipedia.org/wiki/Scytale

We can see that the transpose is connected to seemingly unrelated fields, such as physics and cryptography, and must embody something fundamental indeed.

The Transpose of Products

2008-12-17T09:44:00.000-08:00

Claim: For two matrices A,B, where the product of A and B is well defined, (AB)t = At Bt.

Proof: (AB)t = Bt At = At Bt.

It's a short proof, but the key point is that Bt and At commute because they are both matrices.

Using symmetry to look at the transpose

2008-12-16T19:47:00.000-08:00

One way to define the transpose is to find the main diagonal of a matrix and transpose the matrix elements across it. Alternatively, we can know nothing about the process of finding the transpose and define the transpose from the definition of symmetric and antisymmetric matrices.

symmetric matrix = a matrix which equals its own transpose
antisymmetric matrix = a matrix which equals minus its own transpose

All square matrices can be broken down into the sum of a symmetric and an antisymmetric matrix (we need the fact that 2 transposes equals the identity). This means that if we have a group of matrices under addition which includes all symmetric and antisymmetric matrices, then we know that that group contains all square matrices.

I think we should spend more time investigating groups that are closed under transpose.

Comment on "A Recursive Method"

2008-12-16T18:36:00.000-08:00

I don't think we can use the word "trivial" when taking the transpose of a matrix, especially a 2x2 matrix. Oftentimes, the word "trivial" is used synonymously with "too lazy to show." I feel that this blog should use more rigourous methods of proving properties of transposes. I liked the way you proved the transpose of a 1x1 matrix. If we start using the word "trivial" willy-nilly, I forsee a slippery slope.

I won't let you make a mockery of this blog, Evan.

A Recursive Method

2008-12-16T17:49:00.000-08:00

Group the elements of the matrix into smaller matrices. Transpose the location of the smaller matrices, and then transpose the elements of those matrices themselves.

This method has the advantage of being recursive, so we only need to know how to transpose certain shapes. The base-cases for the recursion is simple: single numbers and 2x2s. The transpose of a single number is the number itself because you can treat it as a one-by-one matrix and thus the number itself is on the diagonal and does not move under transposition, and the transpose of a 2-by-2 is trivial.

Additionally, this implementing this method automatically implements the fact that if the matrix is block-diagonal, you can simply transpose the blocks.

You may think about taking this

2008-12-16T14:02:00.000-08:00

If the previous posts in this blog interest you, you may consider taking this class offered by the UMBC philosophy department:

PHIL476 Modern Philosophy of Mathematical Operations; (3 credits) Grade Method: REG/P-F/AUD.

Prerequiste: PHIL100 (Introduction to Philosophy) and MATH763 (Algebraic Topology) OR MATH764 (Euclidean and Non-Euclidian Geometries)
A philosophical study of some of the current issues associated with mathematical operations and their interpretations in the physical world. The subject lies on the border between mathematics, physics, and philosophy. Topics include Banach and Hilbert interpretations, modern transpose theory, inertia group and factorial analysis. Credit will be granted for only one of the following: PHIL476 (Modern Philosophy of Mathematical Operations) or PHIL477 (Fourier Argument Theory)

Warm Up Exercises

2008-12-16T10:40:00.000-08:00

1. Write a matrix down on a piece of paper. By moving the paper only, can you find the transpose of the matrix?

2. Epistemology of Transposes:

a. If you take the transpose twice, should you have?

b. Prove that no matrix can have the property that taking the transpose twice doesn't give the matrix itself. As a corollary, argue limitations on any all-powerful being, and discuss the implications of such a limitation on the struggle between good and evil, freedom and tyranny, Yankees and Red Sox, and other important religious ideas.

c. If someone takes a transpose of a symmetric matrix in the forest, did it make a noise?

3. Write a general 4x4 matrix in terms of the Dirac gamma matricies and their bilinears. Prove, by the linearity of the transposition operation and direct transposition of those objects, that any 4x4 matrix may be transposed.

A physicist's doubt

2008-12-16T09:33:00.000-08:00

The blog is still in its early stages, but we have seen some insightful methods of taking transposes. We also discussed an example, which involved matrices over the Complex Field (assuming that matrices with real entries were handled in an earlier course).

The discussion though has been quite mathematical till now. I, as an aspiring physicist, was wondering if there exists some physical interpretation to taking a transpose; or is it just interesting mathematics? Though I find the whole field of transpose math really fascinating, I still haven't come across any real physics in this area.

I hope this post would start a discussion and help us explore this fascinating technique further.

2008-12-16T09:31:00.000-08:00

Hassam method : Noone can stop him from taking a transpose.

An example we went over in class

2008-12-15T12:40:00.000-08:00

Ways to take the Transpose

2008-12-15T12:29:00.001-08:00

1) Cohen's Method: Shut up and do it.

2) If the matrix is orthogonal, then find the inverse using

a) Gauss-Jordan elimination
b) Method of Cofactors

3) Iterate Cohen's methods 2n+1 times.

4) If the matrix is hermitian, take the complex conjugate.

more to come...