Editorial for A Math Contest P15 - Matrix Fixed Point - Olympiads Online Judge

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$ $P v = v$ and sums to $1$ $1$ . By rearranging, we can find that:

$\displaystyle Pv = v \implies (P-I)v = 0$ $P v = v ⟹ (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$ $P v = 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$ $⟨ 0, 0, \dots, 0, 1 ⟩$ .

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

Comments

There are no comments at the moment.