Let $A$ be a real $N\times N$ symmetric, positive definite (SPD) matrix with volume $vol(A)=|det(A)|$. Let $B_i$ be the matrix $A$ where row and column $i$ were exchanged by a unit vector $e_i$. Can I check which $B_i$ has the maximal volume $argmax_i(vol(B_i))$ in $O(N^3)$?
Checking by brute force is the best method that comes to my mind which scales as $O(N^4)$, e.g. by exchanging a row/column and computing the determinant from the Cholesky decomposition.
Any method that scales better than brute force, even approximate methods (preferably with error bounds), would be helpful.
So far, I tried deriving an algorithm from Cholesky decomposition and eigen decomposition that reuses information but failed to arrive at something that scales as $O(N^3)$.
Thank you.