Finite arithmetic termination and cost

If $n_1>0$, the initial trailing block $S_1=M_1$ is symmetric positive definite by [F1]. After eliminating the first $j-1$ columns without row swaps, the left augmented block has form $\left(\begin{array}{cc}{I}_{j-1}& A\\ 0& S_j\end{array}\right)$, where $S_j$ is the remaining Schur complement. Write $S_j=\left(\begin{array}{cc}p& r^{\mathsf{T}}\\ r& C\end{array}\right)$. Since $S_j$ is positive definite, $p>0$, so the prescribed diagonal pivot is nonzero. The row operations in column $j$ replace the remaining block by $S_{j+1}=C-r{p}^{-1}{r}^{\mathsf{T}}$. For any nonzero $y$, put $x=-p^{-1}{r}^{\mathsf{T}}y$; then $(x,y)\mathrm{\ne }0$ and $y^{\mathsf{T}}{S}_{j+1}y=(x,y{)}^{\mathsf{T}}{S}_j(x,y)>0$. Hence $S_{j+1}$ is positive definite. Induction proves that every no-row-swap pivot is positive and the error branch is unreachable. Each row operation is invertible; after the last column the left block is the identity, so the right block is exactly $M_1^{-1}$. For $n_1=0$, the inverse is the unique empty matrix and there are no pivot steps.

The input entries are rational. Each row operation uses addition, subtraction, multiplication, or division by a nonzero rational pivot from step 1.1, so every intermediate entry and the final inverse remain rational. The elimination loop has exactly $n_1$ finite iterations; consequently it terminates with an exact rational output.

Dense no-row-swap Gauss–Jordan elimination performs $O(n_1^2)$ row-entry updates per pivot column and hence $O(n_1^3)$ arithmetic operations. Each evolution step uses matrix-vector products with costs $O(n_1^2)$ for $M_1^{-1}d$, $O(n_1{n}_2)$ for each multiplication by $D_1$ or $D_1^{\mathsf{T}}$, and $O(n_2^2)$ for $M_{2}b$. There are exactly $N$ such steps. The matrices $D_0,D_1,D_2,M_1,M_2$ have respectively $n_1{n}_0,n_1{n}_2,n_3{n}_2,n_1^2,n_2^2$ entries; the inverse adds $n_1^2$, and the $N+1$ states add $(N+1)(n_1+n_2)$ entries. Their total is bounded by the stated storage order. When $N=0$, the initial state is returned without an update; when $n_1=0$ or $n_2=0$, the corresponding empty products and loops are finite and the same bounds remain valid. No bit-size or floating-point estimate follows from an arithmetic-operation count.