Because transpose is quite lazy, it need not necessarily result in a quadratic time complexity on every use.
On the other hand, my program needs the entire transposed list, so... ;-)
May be, you should consider some other data structures, for example (borrowed from fido7.ru.math):
data Matrix a = M a [a] [a] (Matrix a) | MEmpty
Here M x ys zs m is a matrix with x in it's upper left corner, ys as it's first row (without x), zs as it's first column (also without x) and m as a remaining submatrix. For example, 1 2 3 4 5 6 is represented as M 1 [2,3] [4] (M 5 [6] [] MEmpty) It takes linear time to transpose these matrices:
transpose (M x ys zs m) = M x zs ys $ transpose m
It's also relatively easy to add these matrices (do it yourself, please), multiply a matrix by a column:
MEmpty `mColMult` ts = map (const 0) ts M x ys zs m `mColMult` (t:ts) = (x*t + sum (zipWith (*) ys ts)) : zipWith (+) (map (* t) zs) (m `mColMult` ts)
and multiply matrices:
M x ys zs m `mMult` M x' ys' zs' m' = M (x * x' + sum (zipWith (*) ys zs')) (zipWith (+) (map (x *) ys') (transpose m' `mColMult` ys)) (zipWith (+) (map (* x') zs) (m `mColMult` zs)) $ (m `mMult` m') `mAdd` (zs `multColRow` ys') where [] `multColRow` _ = mEmpty _ `multColRow` [] = mEmpty (z:zs) `multColRow` (y:ys) = M (z * y) (map (z *) ys) (map (* y) zs) (zs `multColRow` ys)
Hope this helps.