Editorial for A Math Contest P15 - Matrix Fixed Point

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Plasmatic

Our goal is just to find a vector that satisfies $Pv = v$ ~Pv = v~ and sums to $1$ ~1~. By rearranging, we can find that:

$\displaystyle Pv = v \implies (P-I)v = 0$

Thus, we just need to find the kernel of $P-I$ ~P-I~. In particular, since the answer exists and is unique, we know that $\dim \ker(P-I) = 1$ ~\dim \ker(P-I) = 1~ so the basis has exactly one element, and we can just scale the single basis vector so that its sum is $1$ ~1~.

This can be done with Gaussian elimination.

Alternatively, we can just solve directly for the linear system $Pv = 0$ ~Pv = 0~ by further constraining it so that the only result is where $\sum_{i=1}^N v_i = 1$ ~\sum_{i=1}^N v_i = 1~. This can be done by adding an additional row of $1$ ~1~s to $P$ ~P~, and making the target vector $\langle 0, 0, \dots, 0, 1 \rangle$ ~\langle 0, 0, \dots, 0, 1 \rangle~.

Time Complexity: $\mathcal O(N^3)$ ~\mathcal O(N^3)~

Comments

There are no comments at the moment.