IIT KANPUR SAMPLE PAPER 2018

Question

A symmetric matrix X is said to be diagonalizable if we can express it as X = P DP −1 where P is an invertible matrix and D is a diagonal matrix. For a diagonalizable matrix X, how many matrix multiplications would be required to compute X4 = X ∗ X ∗ X ∗ X? Why?

Comments

Two matrix multiplication

At first multiply P with D^4

then multiply the result with P^(-1)

Answer 1

 X = PDP ^{−1  .} Here P is an invertible matrix whose columns consists of eigen vectors of X.
D is a diagonal matrix whose elements are eigen values of X.
Now X= PDP⁻¹
X²=  PDP ⁻¹ PDP ⁻¹
X³= PDP ⁻¹ PDP ⁻¹ PDP ⁻¹
X⁴= PDP ⁻¹ .PDP ⁻¹ .PDP ⁻¹ .PDP ⁻¹
    =PDIDIDIDP −1   (PP-1 = P-1P = I)
     = PD⁴P ⁻¹
Now D⁴ can be obtained just by taking 4^th power of it's diagonal elements (as it is a diagonal matrix so
diag(a₁, ..., a_n) · diag(b₁, ..., b_n) = diag(a₁b₁, ..., a_nb_n).)
So just 2 matrix multiplication is needed as shown by the parenthesis below. 
((PD⁴)P ⁻¹)

Comments

Got it

Thanks