Proof. If (a) and (b) hold, then it is clear that X and Y are isomorphic. Suppose conversely that X and Y are isomorphic. Fix an isomorphism $\varphi \in \mathrm {Hom}_{\Lambda }(X, Y)$ . Then for any $g \in \mathrm {Hom}_{\Lambda }(X, Y)$ , we have $h_{g} := g \circ \varphi ^{-1} \in \mathrm {End}_{\Lambda }(Y)$ and so $g = h_{g} \circ \varphi $ . Hence, $\varphi $ is a generator of $\mathrm {Hom}_{\Lambda }(X, Y)$ over $\mathrm {End}_{\Lambda }(Y)$ and by Lemma 2.3 it is in fact a free generator. Thus, (a) holds. Now, let f be any free generator of $\mathrm {Hom}_{\Lambda }(X, Y)$ over $\mathrm {End}_{\Lambda }(Y)$ . Then there exists $\theta \in \mathrm {Aut}_{\Lambda }(Y)=\mathrm {End}_{\Lambda }(Y)^{\times }$ such that $f = \theta \circ \varphi $ , and hence f is an isomorphism. Thus, (b) holds.

Proof. Set $\mathcal {O}:=\mathcal {O}_{r}(X)$ . Clearly, C is both an R-module and an $\mathcal {O}$ -module. Since X and Y are both full R-lattices in A, there exist nonzero $r,s \in R$ such that $Ys \subseteq X$ and $Xr \subseteq Y$ (see [Reference ReinerRei03, §4]). Thus, $\mathcal {O}r \subseteq C \subseteq \mathcal {O}s^{-1}$ , where $\mathcal {O}r$ and $\mathcal {O}s^{-1}$ are both full R-lattices in A. Hence, C is a full R-lattice and therefore a full $\mathcal {O}$ -lattice in A.

Suppose (a) and (b) hold. Then $Y=XC=X(\mathcal {O}\alpha ) = (X\mathcal {O})\alpha = X \alpha $ . Hence, X and Y are isomorphic since $\alpha \in A^{\times }$ . Suppose conversely that $f: X \rightarrow Y$ is a $\Lambda $ -isomorphism. Then by Lemma 2.2 f extends uniquely to an A-isomorphism $f^{A} : A \rightarrow A$ and hence is given by right multiplication by an element $\alpha \in A^{\times }$ . Thus, $Y = X\alpha $ . Moreover, $C = \{ \lambda \in A \mid X\lambda \subseteq X\alpha \} = \mathcal {O} \alpha $ and $Y = X\alpha = (X\mathcal {O})\alpha = X(\mathcal {O}\alpha ) \,{=}\, XC$ .

Proof. If X and Y are isomorphic, then (a) clearly holds and (b) holds by Proposition 3.1. Suppose conversely that (a) and (b) hold. Let f be a free generator of $\mathrm {Hom}_{\Lambda }(X, Y)$ over $\mathrm {End}_{\Lambda }(Y)$ . Let $\mathfrak {p}$ be a maximal ideal of R. Then there exists an isomorphism $g_{\mathfrak {p}} \in \mathrm {Hom}_{\Lambda _{\mathfrak {p}}}(X_{\mathfrak {p}}, Y_{\mathfrak {p}})$ . Moreover, f extends to a free generator $f_{\mathfrak {p}}$ of $\mathrm {Hom}_{\Lambda _{\mathfrak {p}}}(X_{\mathfrak {p}}, Y_{\mathfrak {p}})$ over $\mathrm {End}_{\Lambda _{\mathfrak {p}}}(Y_{\mathfrak {p}})$ , and so there exists $h_{\mathfrak {p}} \in \mathrm {End}_{\Lambda _{\mathfrak {p}}}(Y_{\mathfrak {p}})$ such that $g_{\mathfrak {p}} = h_{\mathfrak {p}} \circ f_{\mathfrak {p}}$ . Note that $h_{\mathfrak {p}}$ is surjective and thus is in fact an automorphism of $Y_{\mathfrak {p}}$ by [Reference Curtis and ReinerCR81, (5.8)]. Therefore, $f_{\mathfrak {p}}$ is an isomorphism. Since this is true for all choices of $\mathfrak {p}$ , we have that f itself is an isomorphism by [Reference Curtis and ReinerCR81, (4.2)(ii)].

Proof. The first claim and part (a) are both clear. Suppose that $\overline {X} = \overline {\Lambda } \overline {\alpha }$ and that there exists $\beta \in X$ such that $X=\Lambda \beta $ . Since $\alpha \in X=\Lambda \beta $ , there exists $\varepsilon \in \Lambda $ such that $\alpha = \varepsilon \beta $ . Hence, $\overline {\alpha } = \overline {\varepsilon }\overline {\beta }$ , and since each of $\overline {\alpha }$ and $\overline {\beta }$ is a free generator of $\overline {X}$ over $\overline {\Lambda }$ , we must have $\overline {\varepsilon } \in \overline {\Lambda }^{\times }$ . Let $\eta \in \Lambda $ such that $\overline {\eta }=\overline {\varepsilon }^{-1}$ . Then $\varepsilon \eta = 1 + \rho $ , where $\rho \in \operatorname {\mathrm {J}}(A)$ . Moreover, $\rho = \varepsilon \eta - 1 \in \Lambda $ . Since A is Artinian, $\operatorname {\mathrm {J}}(A)$ is a nilpotent ideal (see [Reference Curtis and ReinerCR81, (5.15)]), and so $\rho $ is a nilpotent element. Therefore,

$$\begin{align*}\varepsilon^{-1} = \eta(1 + \rho)^{-1} = \eta(1 - \rho + \rho^{2} - \rho^{3} + \dotsb) \in \Lambda, \end{align*}$$

where the alternating sum is finite. Hence, $\varepsilon \in \Lambda ^{\times }$ and so $\Lambda \alpha = \Lambda \varepsilon \beta = \Lambda \beta = X$ .

Proof. Let $\mathfrak {p}$ be a maximal ideal of $\mathcal {O}$ dividing $\mathrm {Disc}(\Lambda )$ , and write $v_{\mathfrak {p}}(-)$ for the $\mathfrak {p}$ -adic valuation. It follows from [Reference FriedrichsFri00, (3.17)] that the computation of an order $\Lambda ^{(\mathfrak {p})}$ such that $v_{\mathfrak {p}}([\Lambda ^{(\mathfrak {p})} : \Lambda ]_{\mathcal {O}})$ is maximal reduces in polynomial time to the problem of computing the maximal two-sided ideals of an order containing $\mathfrak {p}$ . Now, fix an order $\Gamma $ . Then the maximal two-sided ideals of $\Gamma $ containing $\mathfrak {p}$ are the preimages of the maximal two-sided ideals under the canonical projection $\Gamma \to (\Gamma /\mathfrak {p}\Gamma )/{\operatorname {\mathrm {J}}(\Gamma /\mathfrak {p}\Gamma )}$ (see [Reference FriedrichsFri00, (5.23)]). As a decomposition of this $(\mathcal {O}/\mathfrak {p})$ -algebra into simple components and therefore the maximal two-sided ideals can be found in probabilistic polynomial time by [Reference Friedl and RonyaiFR85, 1.5 B], an order $\Lambda ^{(\mathfrak {p})}$ can be determined in probabilistic polynomial time. By [Reference FriedrichsFri00, (3.19)] the order $\sum _{\mathfrak {p}} \Lambda ^{(\mathfrak {p})}$ is maximal, where $\mathfrak {p}$ runs over the maximal ideals of $\mathcal {O}$ dividing $\mathrm {Disc}(\Lambda )$ . Therefore, the computation of a maximal order $\mathcal {M}$ containing $\Lambda $ reduces in probabilistic polynomial time to $\mathsf {Factor}(\mathrm {Disc}(\Lambda ))$ .

Proof. The algorithm is presented in [Reference Bley and JohnstonBJ08, §5] and works by reducing the problem to the computation of a Steinitz form of an $\mathcal {O}$ -lattice of rank n, which can be performed in probabilistic polynomial time by Corollary A.3.

Proof. By decomposing $\mathcal {M}$ using the central primitive idempotents of A, it suffices to consider the case $A = \mathrm {Mat}_{n}(K)$ , in which we must have $\mathcal {O}_{C} = \mathcal {O}$ . Then the reduced norm map $\mathrm {nr}: A \rightarrow K$ is just the usual determinant map. Moreover, using Lemma 6.2, we can and do assume that $\mathcal {M} = \mathcal {M}_{\mathfrak a, n}$ is a nice maximal order. Since $\alpha = \operatorname {diag}(a,1,\dotsc ,1) \in \mathcal {M}_{\mathfrak a, n}^{\times }$ satisfies $\mathrm {nr}(\alpha ) = a$ , the claim follows.

Proof. By decomposing $\mathcal {M}$ using the central primitive idempotents of A, it suffices to consider the case $A = \mathrm {Mat}_{n}(K)$ , in which we must have $\mathcal {O}_{C} = \mathcal {O}$ . Let X be a full $\mathcal {M}$ -lattice in A. Let $e_{11} \in A$ be the matrix with the top-left entry equal to $1$ and all other entries equal to $0$ . Using Lemma 6.2, we can and do assume that $\mathcal {M} = \mathcal {M}_{\mathfrak a, n}$ is a nice maximal order. By [Reference Bley and JohnstonBJ08, Corollary 5.4], it is sufficient to check whether the Steinitz class of the $\mathcal {O}$ -module $e_{11}X$ is equal to $[\mathfrak a^{-1}]$ , which amounts to testing whether a certain ideal of $\mathcal {O}$ is principal.

Proof. Consider the finitely generated $\mathcal {O}/\mathfrak {p}$ -algebra $R_{\mathfrak {p}} := \Lambda /\mathfrak {p} \Lambda \cong \Lambda _{\mathfrak {p}} / \mathfrak {p} \Lambda _{\mathfrak {p}}$ . It follows from [Reference Friedl and RonyaiFR85, 1.5 A] that the Jacobson radical $J_{\mathfrak {p}} = \operatorname {\mathrm {J}}(R_{\mathfrak {p}})$ can be determined in polynomial time. Let $\overline {R}_{\mathfrak {p}} = R_{\mathfrak {p}}/J_{\mathfrak {p}}$ . By Lemma 2.3 and Nakayama’s lemma, $X_{\mathfrak {p}}$ is free over $\Lambda _{\mathfrak {p}}$ if and only if $\overline {X}_{\mathfrak {p}} := (X/\mathfrak {p}X)/J_{\mathfrak {p}}(X/\mathfrak {p}X) \cong (X_{\mathfrak {p}}/\mathfrak {p}X_{\mathfrak {p}})/J_{\mathfrak {p}}(X_{\mathfrak {p}}/\mathfrak {p}X_{\mathfrak {p}})$ is free of rank $1$ over $\overline {R}_{\mathfrak {p}}$ . Using algorithms of Friedl–Rónyai [Reference Friedl and RonyaiFR85, 1.5 B] and Ronyai [Reference RonyaiRon87, Theorem 6.2], one can determine an isomorphism of $\overline {R}_{\mathfrak {p}}$ with a product of matrix algebras over finite fields $k_{i}$ in probabilistic polynomial time. The final steps are just linear algebra over finite fields.

Proof. We use Proposition 6.5 together with the reduction to the free rank $1$ case given by Proposition 3.1. Both $\mathrm {End}_{\Lambda }(Y)$ and $\mathrm {Hom}_{\Lambda }(X, Y)$ can be determined as described in [Reference Hofmann and JohnstonHJ20, §7.3] using pseudo-Hermite normal form and pseudo-Smith normal form computations, which are probabilistic polynomial time by [Reference Biasse, Fieker and HofmannBFH17, Theorem 34, Proposition 43]. Using Proposition 6.5 one can determine in probabilistic polynomial time whether the $(\mathrm {End}_\Lambda (Y))_{\mathfrak {p}}$ -lattice $(\mathrm {Hom}_\Lambda (X, Y))_{\mathfrak {p}}$ is free of rank $1$ . If not, then $X_{\mathfrak {p}}$ and $Y_{\mathfrak {p}}$ are not isomorphic over $\Lambda _{\mathfrak {p}}$ . If so, then the algorithm returns a free generator $f \in \mathrm {Hom}_\Lambda (X, Y)$ of $(\mathrm {Hom}_\Lambda (X, Y))_{\mathfrak {p}}$ over $(\mathrm {End}_\Lambda (Y))_{\mathfrak {p}}$ . Then $X_{\mathfrak {p}} \cong Y_{\mathfrak {p}}$ over $\Lambda _{\mathfrak {p}}$ if and only if the localisation $f_{\mathfrak {p}} \colon X_{\mathfrak {p}} \to Y_{\mathfrak {p}}$ is an isomorphism.

Proof. Let $\mathrm {MaxSpec}(\mathcal {O})$ denote the set of all maximal ideals of $\mathcal {O}$ . Let $\mathfrak {S}= \{ \mathfrak {p}_{1}, \ldots , \mathfrak {p}_{n} \}$ be the subset consisting of ideals that divide $\mathcal {O} \cap \mathfrak {f}$ (note that this is a proper nonzero ideal of $\mathcal {O}$ ), and let $\mathfrak {T} = \mathrm {MaxSpec}(\mathcal {O}) \setminus \mathfrak {S}$ . Observe that, for every $\mathfrak {p} \in \mathfrak {T}$ , we have $\mathfrak {f}_{\mathfrak {p}} = \Lambda _{\mathfrak {p}}=\mathcal {M}_{\mathfrak {p}}$ , and so $X_{\mathfrak {p}}$ is free over $\Lambda _{\mathfrak {p}}$ by [Reference ReinerRei03, (18.10)]. Moreover, for each i, checking whether $X_{\mathfrak {p}_i}$ is free over $\Lambda _{\mathfrak {p}_i}$ and, if so, computing $\omega _{i} \in X$ such that $X_{\mathfrak {p}_i} = \Lambda _{\mathfrak {p}_i} \omega _{i}$ , can be performed in probabilistic polynomial time by Proposition 6.5. In particular, if this step is completed successfully, then X is locally free over $\Lambda $ .

By [Reference CohenCoh00, Proposition 1.3.11], elements $\beta _{1}, \ldots , \beta _{n} \in \mathcal {O}$ such that for each i, we have

$$\begin{align*}\beta_i \equiv 1 \bmod{\mathfrak{p}_i} \quad \text{ and } \quad \beta_i \equiv 0 \bmod{\mathfrak{p}_j} \text{ for } 1 \le j \le n, j \ne i \end{align*}$$

can be computed in polynomial time. For each i, let $\nu _i \in \mathcal {O} \setminus \mathfrak {p}_i$ be an element such that $X \omega _i^{-1} \nu _i \subseteq \Lambda $ . Then $X\xi \subseteq \Lambda $ , where $\xi := \sum _{i=1}^{n} \beta _{i} \omega _{i}^{-1} \nu _{i}$ . By construction we have $(X \xi )_{\mathfrak {p}_{i}} = \Lambda _{\mathfrak {p}_{i}}$ for each i. Moreover, $\mathfrak {f}_{\mathfrak {p}} = \Lambda _{\mathfrak {p}}$ for all $\mathfrak {p} \in \mathfrak {T}$ . Therefore, $(X\xi + \mathfrak {f})_{\mathfrak {p}} = \Lambda _{\mathfrak {p}}$ for all $\mathfrak {p} \in \mathrm {MaxSpec}(\mathcal {O})$ , and so $X\xi + \mathfrak {f} = \Lambda $ by [Reference ReinerRei03, (4.21)].

Proof. Let k denote the finite field $\mathcal {O}/(\mathfrak {p} \cap \mathcal {O})$ . Let $R = \Lambda /(\mathfrak {p} \Lambda + \mathfrak {f})$ , and note that this is annihilated by $\mathfrak {p} \cap \mathcal {O}$ . Thus, R is a k-algebra such that $\dim _{k} R \leq d$ . In particular, R is Artinian, so its Jacobson radical $J = \operatorname {\mathrm {J}}(R)$ is nilpotent by [Reference Curtis and ReinerCR81, (5.15)]. Since we have a decreasing filtration $J \supseteq J^2 \supseteq \cdots \supseteq J^d$ and $\dim _k(J) \le d-1$ , we obtain $J^{d}=0$ . By [Reference Bley, Boltje, Hess, Pauli and PohstBB06, Lemma 3.6] and the same reasoning as in [Reference Bley, Boltje, Hess, Pauli and PohstBB06, §3.7], we have an exact sequence

$$\begin{align*}1 + J \longrightarrow \operatorname{\mathrm{G}}(R) \longrightarrow \operatorname{\mathrm{G}}(R/J) \longrightarrow 1. \end{align*}$$

We first discuss the computation of generators for $1 + J$ . To this end, let $l \in \mathbb {Z}_{\geq 0}$ be minimal subject to the condition $J^{2^l} = 0$ and note that $2^{l} \leq 2d$ . Consider the filtration

$$\begin{align*}1 + J \supseteq 1 + J^2 \supseteq \dotsb \supseteq 1 + J^{2^{l - 1}} \supseteq 1. \end{align*}$$

Generators of J can be determined in polynomial time using the algorithms of [Reference Friedl and RonyaiFR85, 1.5 A]. For each $i = 0,\dotsc ,l-1$ , the map $\overline {x} \mapsto \overline {x-1}$ induces an isomorphism

$$\begin{align*}(1 + J^{2^i})/(1 + J^{2^{i+1}}) \longrightarrow J^{2^i}/J^{2^{i+1}} \end{align*}$$

of abelian groups, and so it follows that we can find generators of $1 + J$ in polynomial time. For each $i = 0, \dotsc , l - 1$ the number of generators of $J^{2^i}/J^{2^{i + 1}}$ is bounded by $\dim _k(J^{2^i}/J^{2^{i+1}}) [K : \mathbb {Q}]$ . Now, summing over $i = 0,\dotsc ,l-1$ shows that $1 + J$ is generated by at most $\dim _k(J) [K : \mathbb {Q}] \leq (d-1) [K : \mathbb {Q}]$ elements.

Using algorithms of [Reference Friedl and RonyaiFR85, 1.5 B] and [Reference RonyaiRon87, Theorem 6.2], one can determine an isomorphism $R/J \cong \prod _{1 \leq i \leq r} \mathrm {Mat}_{n_{i}}(k_{i})$ with a product of matrix algebras over finite fields $k_{i}$ in probabilistic polynomial time. Since

$$\begin{align*}\operatorname{\mathrm{G}}(R/J) \cong \prod_{1 \leq i \leq r} \operatorname{\mathrm{G}}(\mathrm{Mat}_{n_i}(k_i)), \end{align*}$$

this problem reduces to the computation of each $\operatorname {\mathrm {G}}(\mathrm {Mat}_{n_i}(k_i))$ , which we claim is generated by at most $2$ elements. If $\operatorname {\mathrm {G}}{} = K_1$ , then the claim follows from the fact that the canonical maps $k_{i}^{\times } \to K_{1}(k_{i}) \to K_1(\mathrm {Mat}_{n_i}(k_i))$ are isomorphisms. If $\operatorname {\mathrm {G}}{} = (-)^\times $ , then the claim follows from [Reference TaylorTay87], where it is shown that given a primitive element of $k_i$ one can write down directly a two element generating set of $\mathrm {GL}_{n_i}(k_i)$ . Since $\dim _{k}(R/J) \leq d$ we have $r \leq d$ and $[k_i : k] \leq d$ for each i. Finally, note that $\mathcal {O}/(\mathcal {O}\cap \mathfrak {p}) = \mathcal {O} / (\mathcal {O}\cap \mathfrak {P})$ since $\mathcal {O}\subseteq \Lambda $ implies $\mathcal {O}\cap \mathfrak {p}= \mathcal {O}\cap \mathfrak {P}\cap \Lambda = \mathcal {O}\cap \mathfrak {P}$ . In particular, $G(R/J)$ is generated by at most $2r \leq 2d$ elements.

Proof. If $e_{\mathfrak {p}}=1$ , we clearly have $\mathfrak {p} = \mathfrak {q}$ , and so $m=0$ . If $e_{\mathfrak {p}}> 1$ , we let $l \in \mathbb {Z}_{>0}$ be minimal subject to the condition $\mathfrak {p}^{2^l} \subseteq \mathfrak {q}$ . Then there exists a filtration

$$\begin{align*}\mathfrak{p} \Lambda + \mathfrak{f} \supseteq (\mathfrak{q} + \mathfrak{p}^2)\Lambda + \mathfrak{f} \supseteq \dotsb \supseteq (\mathfrak{q} + \mathfrak{p}^{2^{l - 1}})\Lambda + \mathfrak{f} \supseteq \mathfrak{q} \Lambda + \mathfrak{f}. \end{align*}$$

For each $i = 0,\dotsc ,l-1$ , the map $\overline {x} \mapsto \overline {x-1}$ induces an isomorphism

$$\begin{align*}\frac{1 + (\mathfrak{q} + \mathfrak{p}^{2^i})\Lambda + \mathfrak{f}} {1 + (\mathfrak{q} + \mathfrak{p}^{2^{i+1}})\Lambda + \mathfrak{f}} \longrightarrow \frac{(\mathfrak{q} + \mathfrak{p}^{2^i})\Lambda + \mathfrak{f}}{(\mathfrak{q} + \mathfrak{p}^{2^{i+1}})\Lambda + \mathfrak{f}} \end{align*}$$

of abelian groups. Hence, any $\mathbb {Z}$ -basis of the right-hand side yields generators of the left-hand side. It remains to bound l. For every with $\mathfrak {P} \cap \Lambda = \mathfrak {p}$ , the inclusion $\mathfrak {p}^{e_{\mathfrak {p}}} = (\mathfrak {P} \cap \Lambda )^{e_{\mathfrak {p}}} \subseteq \mathfrak {P}^{e_{\mathfrak {p}}} \cap \Lambda \subseteq \mathfrak {P}^{e_{\mathfrak {P}}} \cap \Lambda $ holds. Hence, $\mathfrak {p}^{e_{\mathfrak {p}}} \subseteq \mathfrak {q}$ and therefore $2^{l} \leq 2e_{\mathfrak {p}}$ , which gives $l \leq 1 + \log _{2}(e_{\mathfrak {p}})$ .

Since any quotient $((\mathfrak {q} + \mathfrak {p}^{2^i})\Lambda + \mathfrak {f}) / ((\mathfrak {q} + \mathfrak {p}^{2^{i+1}})\Lambda + \mathfrak {f})$ is generated by at most $d [K : \mathbb {Q}]$ elements, the quotient $(1 + \mathfrak {p} \Lambda + \mathfrak {f})/(1 + \mathfrak {q} \Lambda + \mathfrak {f})$ is generated by at most $(1 + \log _{2}(e_{\mathfrak {p}})) d [K : \mathbb {Q}]$ elements.

Proof. Using the factorisation of $\mathfrak {g} = \mathfrak {f} \cap \mathcal {O}_{C}$ , one can determine the sets of ideals

,

and

in polynomial time. Since

, the claim follows from the reduction to the computation of $\mathrm {G}(\Lambda /(\mathfrak {q}\Lambda + \mathfrak {f}))$ for each

discussed at the beginning of the section, the exact sequence (5), Lemmas 6.9 and 6.10 and the following computation

The inequality $(*)$ is a consequence of

which, in turn, is immediate from

.

Proof. Write $\mathbf {v} = (v_1,\dotsc ,v_n)^t$ . Note that as $\mathcal {O}/\mathfrak {q}$ is local; $\mathbf {v}$ being unimodular implies that there exists $1 \leq i \leq n$ such that $v_i \in (\mathcal {O}/\mathfrak {q})^\times $ .

Case 1: If $v_1 \in (\mathcal {O}/\mathfrak {q})^\times $ , then $e_{21}(-v_1^{-1}v_2) \dotsm e_{n1}(-v_1^{-1}v_n) \mathbf {v}$ has the required form.

Case 2: If $v_i \in (\mathcal {O}/\mathfrak {q})^\times $ with $1 < i \leq n$ , then after multiplying $\mathbf {v}$ by $e_{1i}(1) e_{i1}(-1) e_{1i}(1)$ on the left, the first entry will be invertible and we are in the first case.

Proof. The first part follows by repeatedly applying Lemma 7.1 to V and submatrices of V. If V is lower triangular, then we are always in Case 1 of the proof of Lemma 7.1 and thus easily see that the resulting matrix is diagonal.

Proof. From [Reference RosenbergRos94, 2.1.3 Corollary] it follows that a diagonal matrix with diagonal $(1,\dotsc ,1,v,v^{-1},1,\dotsc ,1)$ with $v \in (\mathcal {O}/\mathfrak {q})^\times $ is the product of six elementary matrices since

$$\begin{align*}\begin{pmatrix} v & 0 \\ 0 & v^{-1} \end{pmatrix} = \begin{pmatrix} 1 & v \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ -v^{-1} & 1 \end{pmatrix} \begin{pmatrix} 1 & v \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & -1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & -1 \\ 0 & 1 \end{pmatrix}. \end{align*}$$

Hence, we can left-multiply V with $6(n - 1)$ elementary matrices to obtain $(1,1,\dotsc ,1)^t$ .

Proof. Using Lemma 7.2 there exist elementary matrices $E_1, \dotsc ,E_{k'}$ such that $U := E_1\dotsm E_{k'} V$ is an upper triangular matrix. Using Lemma 7.2 again, this time applied to the lower diagonal matrix $U^t$ , we can find elementary matrices $F_1,\dotsc ,F_l$ such that $D = UF_1\dotsm F_l$ is a diagonal matrix. Finally, invoking Lemma 7.3 yields elementary matrices $\tilde E_1,\dotsc ,\tilde E_{\tilde k}$ such that $\tilde E_1\dotsm \tilde E_{\tilde k} D$ is the $n \times n$ identity matrix.

Proof. In the case that $\mathfrak {g}$ is a prime ideal power, this follows from Proposition 7.4. Now, let $\mathfrak {g} = \mathfrak {q}_{1}\dotsm \mathfrak {q}_{m}$ be the product of m coprime prime ideal powers, and consider a matrix $V \in \mathrm {SL}_n(\mathcal {O}/\mathfrak {g})$ . For each $1 \leq i \leq m$ we can determine in polynomial time a factorisation of $V \in \mathrm {SL}_n(\mathcal {O}/\mathfrak {q}_i)$ into elementary matrices. The result follows by observing that the canonical map

$$\begin{align*}\mathrm{E}_n(\mathcal{O}/\mathfrak{g}) \to \prod_{i=1}^m \mathrm{E}_n(\mathcal{O}/\mathfrak{q}_i) \end{align*}$$

is an isomorphism by the Chinese remainder theorem which can be made effective in polynomial time ([Reference CohenCoh00, Proposition 1.3.11]).

Proof. For $V \in \mathrm {Mat}_n(\mathcal {O})$ we write

$$\begin{align*}\def\arraystretch{1.2} V = \left( \begin{array}{c|c}V_1 & x \\ \hline y & d \end{array} \right) \end{align*}$$

with $V_1 \in \mathrm {Mat}_{n-1}(\mathcal {O}), x,y^t \in \mathcal {O}^{n-1}$ and $d \in \mathcal {O}$ . Then

$$\begin{align*}\def\arraystretch{1.2} \psi_{1}(V) = \left( \begin{array}{c|c}V_1 & \xi^{-1}x \\ \hline \xi b y & bd \end{array} \right). \end{align*}$$

Let $I_m \in \mathrm {Mat}_m(\mathcal {O})$ denote the identity matrix.

Case 1: If $\def \arraystretch {1.2} \overline {E} = \left ( \begin {array}{c|c} e_{ij}(\bar a) & 0 \\ \hline 0 & 1 \end {array} \right ) $ with $a \in \mathcal {O}$ , then $\def \arraystretch {1.2} \overline {\psi }_1(\overline {E}) = \left ( \begin {array}{c|c} e_{ij}(\bar a) & 0 \\ \hline 0 & \bar b \end {array} \right ) $ and a lift is given by

$$\begin{align*}\left( \begin{array}{c|c} e_{ij}(a) & 0 \\ \hline 0 & 1 \end{array} \right). \end{align*}$$

Case 2: If $\def \arraystretch {1.2} \overline {E} = \left ( \begin {array}{c|c} \overline {I}_{n-1} & \bar x \\ \hline 0 & 1 \end {array} \right ) $ with $\bar x^t = (0,\ldots ,0,\bar a, 0, \ldots , 0), a \in \mathcal {O}$ , then $\def \arraystretch {1.2} \overline {\psi }_{1}(\overline {E}) = \left ( \begin {array}{c|c} \overline {I}_{n-1} & \overline {\xi ^{-1} x}\\ \hline 0 & \bar b \end {array} \right ) $ and a lift is given by

$$\begin{align*}\left( \begin{array}{c|c} I_{n-1} & {\xi^{-1} x}\\ \hline 0 & 1 \end{array} \right). \end{align*}$$

Note that in this case $\xi ^{-1}a \in \mathfrak {b}\mathfrak {a}^{-1} \subseteq \mathfrak {a}^{-1}$ .

Case 3: If $\overline {E} = \left ( \begin {array}{c|c} \overline {I}_{n-1} & 0 \\ \hline \bar y & 1 \end {array} \right )$ with $\bar y = (0,\ldots ,0,\bar a, 0, \ldots , 0), a \in \mathcal {O}$ , then $\def \arraystretch {1.2} \psi _{1}(\overline {E}) = \left ( \begin {array}{c|c} \overline {I}_{n-1} & 0 \\ \hline \overline {\xi by} & \bar b \end {array} \right )$ and a lift is given by

$$\begin{align*}\left( \begin{array}{c|c} I_{n-1} & 0 \\ \hline \xi by & 1 \end{array} \right). \end{align*}$$

Here we note that $\xi ba \in \xi \mathfrak {b} = \mathfrak {a}$ .

Proof. By Corollary 7.5 we can find elementary matrices $E_1,\dotsc ,E_r \in \mathrm {Mat}_n(\mathcal {O}/\mathfrak {g})$ with $\overline {\psi }_2(V) = E_1\dotsm E_r$ . Applying $\overline {\psi }_{1}$ we obtain $V = \overline {\psi }_1(E_1)\dotsm \overline {\psi }_1(E_r)$ . Moreover, by Lemma 7.7, each of the matrices $\overline {\psi }_1(E_i)$ can be lifted to a matrix $U_i \in \mathcal {M}^\times $ with $\mathrm {nr}(U_{i}) = 1$ . Thus, we can and do take $U := \prod _{i}U_{i}$ .

Proof. By decomposing $\mathcal {M}$ using the central primitive idempotents, it is sufficient to consider the case $A = \mathrm {Mat}_{n}(K)$ . By Lemma 6.2, we can and do assume that $\mathcal {M} = \mathcal {M}_{\mathfrak a, n}$ is a nice maximal order. Thus, the result follows from Proposition 7.8.