Finite aggregation AMG preserves the SPD matrix class and returns a status

At any aggregation pass the unassigned set $U$ is finite and nonempty. The selected smallest vertex $i$ belongs to the new aggregate, so at least one vertex is removed. No previously removed vertex can reappear because every neighbour is intersected with $U$. Thus the aggregates are pairwise disjoint and, when the finite loop ends at $U=\mathrm{\varnothing }$, cover all current indices. Each aggregate is nonempty. If $Pz=0$, choose any row index in aggregate $r$; its row has a single $1$ in column $r$, so that component of $Pz$ is $z_r=0$. This holds for every $r$, hence $P$ has full column rank.

By [F2] and step 1.1, $A_{\mathrm{\ell }+1}=P_{\mathrm{\ell }}^{\mathsf{T}}{A}_{\mathrm{\ell }}{P}_{\mathrm{\ell }}$ is SPD. For distinct aggregate columns $r\mathrm{\ne }s$, disjointness gives $(A_{\mathrm{\ell }+1}{)}_{rs}={\sum }_{i\in C_r}{\sum }_{j\in C_s}{a}_{ij}^{(\mathrm{\ell })}\le 0,$ since $i\mathrm{\ne }j$ in every summand and the fine matrix has nonpositive off-diagonal entries. Symmetry follows from symmetry of $A_{\mathrm{\ell }}$. Induction over successful levels proves the same matrix class at each returned level.

Each aggregation pass is finite by step 1.1. A pass is attempted only when $\mathrm{\ell }+1\le L$, so the number of attempts is an integer at most $\lfloor L\rfloor$. At each outer iteration, step 1 returns coarse-reached when $n_{\mathrm{\ell }}\le n_{\min }$; otherwise the cap test in [F1] returns level-cap when $\mathrm{\ell }+1>L$. If neither branch applies, a pass is performed and either $n_{\mathrm{\ell }+1}\ge n_{\mathrm{\ell }}$ returns coarsening-stalled, or the procedure advances to the next level. These ordered branches exhaust the procedure, so it terminates with exactly one listed status.

The preceding steps establish the partition, rank, matrix-class and status claims. No step asserts a contraction factor.