Matrix Transpose

March 20, 2015

There is a simple and quick algorithm based on sorting:

1) Make a pass through the input, prepending the row number and column number to each field. Output is a three-tuple of row, column, value for each cell in the matrix. Write the output to a temporary file.

2) Sort the temporary file by column, then row.

3) Make a pass through the sorted temporary file, reconstructing the transposed matrix.

Here’s the code:

$ echo '11 12 13 14
> 21 22 23 24
> 31 32 33 34' |
> awk '{ for (i=1; i sort -n |
> awk ' NR>1 && $2==1 { print "" }; { printf "%s ", $3 }; END { print "" }'
11 21 31
12 22 32
13 23 33
14 24 34

A little three-line shell script is all you need to do the transpose. It’s nice to write programs when someone else has already done the hard work. You can run the program at http://ideone.com/JGTbex.

Advertisements

Pages: 1 2

5 Responses to “Matrix Transpose”

  1. Rutger said

    In Python, assuming that we cán fit one row in memory..

    file_like_object = []
    file_like_object.append([11,12,13,14,11,21,31])
    file_like_object.append([21,22,23,24,12,22,32])
    file_like_object.append([31,32,33,34,13,23,33])
    file_like_object.append([14,24,34])
    
    
    max_row_length = 1
    i = 0
    while i < max_row_length:
    	for row in file_like_object:
    		if len(row) > max_row_length:
    			max_row_length = len(row)
    		if i < len(row):
    			print row[i],
    	print
    	i += 1
    
  2. matthew said

    If it’s a square matrix with the row and column lengths 2^n, we can transpose in just n linear scans through the array, zipping together the front and back halves (like a riffle shuffle):

    zipl (a:s) (b:t) = a:b:zipl s t
    zipl _ _ = []

    trans 0 m s = s
    trans n m s = trans (n-1) m (zipl (take m s) (drop m s))

    test n = trans n (2^(2*n-1)) [0..2^(2*n)]
    main = print (test 2)

  3. matthew said

    Actually, this will work for any matrix where the number of rows is a power of two. Tidying up the previous solution (now trans m n s expects m to be half the total array size, n is the number of rows, s is the array):

    zipl (a:s) (b:t) = a:b:zipl s t
    zipl _ _ = []

    trans m 1 s = s
    trans m n s = trans m (n `div` 2) (zipl (take m s) (drop m s))

    main =
    print [0..23] >>
    print (trans 12 8 [0..23]) >>
    print (trans 12 4 [0..23])

  4. matthew said

    Just trying to get some nicer formatting:

    zipl (a:s) (b:t) = a:b:zipl s t
    zipl _ _ = []
    
    trans m 1 s = s
    trans m n s = trans m (n `div` 2) (zipl (take m s) (drop m s))
    
    main =
    print [0..23] >>
    print (trans 12 8 [0..23]) >>
    print (trans 12 4 [0..23])
    
  5. matthew said

    And where the number of columns is 2^n, we can invert the process – output all even elements, then all odd elements, repeat n times. In Haskell:

    pairs (a:b:s) = (a,b):pairs s
    pairs _ = []
    
    trans 0 s = s
    trans n s = trans (n-1) (uncurry (++) $ unzip $ pairs s)
     
    main =
         print [0..23] >>
         print (trans 1 [0..23]) >>
         print (trans 2 [0..23]) >>
         print (trans 3 [0..23])
    

    Or maybe this corresponds better to how we might do it with files:

    evens (a:s) = a : odds s
    evens _ = []
    odds (_:s) = evens s
    odds _ = []
    
    trans 0 s = s
    trans n s = trans (n-1) (evens s ++ odds s)
    
    main =
         print [0..23] >>
         print (trans 1 [0..23]) >>
         print (trans 2 [0..23]) >>
         print (trans 3 [0..23])
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: