Consider $S\in\mathbb{R}^{n\times n}$ whose nonzero elements have the following pattern for $n = 8$: $$\begin{pmatrix} 1 & 0 & 0 & 0 & \mu_1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & \mu_2 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & \mu_3 & 0 & 0 & 0\\ 0 & 0 & 0 & \alpha & \beta & 0 & 0 & 0\\ 0 & 0 & 0 & \gamma & \delta & 0 & 0 & 0\\ 0 & 0 & 0 & \delta_1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & \delta_2 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & \delta_3 & 0 & 0 & 0 & 1\\ \end{pmatrix}$$ The pattern generalizes to any $n$ easily. Assume that for any $n$, $S$ is a nonsingular matrix.
a.) We have considered several basic transformations (Gauss transforms, Gauss Jordan transforms, elementary permutations, Household reflectors) that can be used to compute the factorizations efficiently.
Using what ever combination of these transformations, describe an algorithm to compute stably a factorization of $S$ for any $n$ that can be used to solve $Sx = b$. Your algorithm should be designed to require as few computations as possible. Your solution must include a description of how you exploit the structure of the matrix and its factors.
Attempted solution - Right off the back to me this matrix looks ugly so I am thinking of putting it into a better form so essentially applying permutations to the matrix. In part of my professors solution he says: One way to approach this problem performs an priori symmetric permutation i.e., re ordering the rows and columns with the same permutation. Consider $P^T S P$ where $$P = \begin{pmatrix} e_1 & e_2 & e_3 & e_6 & e_7 & e_8 & e_4 & e_5\end{pmatrix}$$ I am wondering about the logic of how we gets $P$. Note that $e_i$ just denotes the position of the $1$. For example $e_1$ is just an $8$ by $1$ matrix with $1$ in the first entry followed by $0$'s in the remaining entries.
So that is question $1$ for me.
Now applying this we get $$\tilde{S} = P^T S P = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & \mu_1\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & \mu_2\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & \mu_3\\ 0 & 0 & 0 & 1 & 0 & 0 & \delta_1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & \delta_2 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & \delta_3 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & \alpha & \beta\\ 0 & 0 & 0 & 0 & 0 & 0 & \gamma & \delta\\ \end{pmatrix}$$ Alright, so now we have a better form to the matrix. Now I want to apply the Gauss transform to this matrix in order to get $U$ in the $LU$ factorization. Now since all the nonzero entries that we need to stress over is in the 2 last columns I believe we just need to find $M_6$ and $M_7$ to get my $U$ i.e., I am applying $$M_{n-1}\ldots M_1 A^{(n-1)} = U$$ I hope that is clear if not please let me know. Now once I do this correctly I can simply apply a forward and backward solve to compute the system $Sx = b$.
Any suggestions or comments in regards to this question are greatly appreciated.