arrow structure matrices and Sherman-Morrison-Woodbury I have two questions regarding "arrow structured" matrices and I'll be grateful if you can give more insights about them:
1- If $A \in \mathbb{R}^{n \times n}$ is SPD and has the arrow structure, e.g. $$A=\begin{bmatrix}x& x& x& x\\x& x& 0& 0\\x &0 &x &0\\x &0& 0 & x\end{bmatrix}$$ then using Sherman-Morrison-Woodbury how can we solve $Ax=b$ with $O(n)$ flops?
2- How to define a permutation matrix $P$ i.e. $PAP' = GG'$ so that the Cholesky factorization can be computed with $O(n)$ flops?
Thanks
 A: The arrow shape $n\times n$ symmetric (positive definite) matrix $A=(a_{ij})$ can be written in the form
$$
A=D+ce_1^T+e_1c^T=D+[c,e_1][e_1,c]^T=D+C\Pi C^T,
$$
where $c=[0,a_{21},\ldots,a_{n1}]^T$, $e_1=[1,0,\ldots,0]^T$, and $\Pi=\begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix}$. Using the Woodbury formula, we have
$$
A^{-1}=(D+C\Pi C^T)^{-1}=D^{-1}-D^{-1}C(\Pi^{-1}+C^TD^{-1}C)^{-1}C^TD^{-1}.
$$
Applying the inverse of $A$ hence involves:


*

*application of $D^{-1}$, that is, simple diagonal scaling of the complexity of $O(n)$,

*solving the $2\times 2$ system with 
$$M=\Pi+C^TD^{-1}C=\begin{bmatrix}a_{11}^{-1}&1\\1&\sum_{i=2}^na_{ii}^{-1}a_{i1}^2\end{bmatrix}$$
(note that $\Pi^{-1}=\Pi$).


For solving $Ax=b$, you do:


*

*Compute $f=D^{-1}b$.

*Compute $g=C^Tf=\begin{bmatrix}c^T\\e_1^T\end{bmatrix}f$.

*Solve $Mh=g$.

*Compute $k=D^{-1}Ch=D^{-1}(h_1c+h_2e_1)$.

*Set $x=f-k$.


This kind of the arrow-shape matrix, if using the Cholesky factorisation without permutations, has full triangular factors (in the first step, in order to eliminate the first column, you introduce nonzeros generally in each position of the matrix). Hence in this case, the complexity of the elimination would be $O(n^3)$.
To avoid this, it is sufficient to permute $A$ such that the arrow is directed to the south-west corner instead of the north-east one, that is, you permute the first and last row (and symmetrically the first and last column). Then you need only to eliminate the last row which can be done with $O(n)$ operations.
