Is there any way other than directly take the transpose of PA?

Because if I do it this way, I found that I have to calculate the inverse of P which is definitely not very desirable considering it is very costly.

Any clue is appreciated. Thanks!

# Past test question Q1

**chushaok**#1

**karshak1**#2

P is a permutation matrix so the inverse of P is just its transpose.

Really not sure on this

At x = b

At Pt P x = b since Pt P = I

(PA)t z = b let z = Px

(LU)t z = b

Ut Lt z = b

=> Ut c = b (1) solve for c

=> Lt z = c (2) solve for z

=> P x = z (3) solve for x

- is forward substitution using matrix Ut, no extra computation, when we need i j entry of Ut we just use j i entry of U. n^2/2 flops and n divisions
- is backward substitution using matrix Lt, same again as above n^2/2 flops and 0 divisions
- I think this is just n operations. If P is stored as a perm vector

for i = 1 to n

x[permP[i]] = z[i]

endfor

(if permP = [4, 3, 1, 2] and z = [40, 30, 10, 20]t then x = [10, 20, 30, 40]t )