jaxvacua.util.extended_euclidean

extended_euclidean(w)

Computes Bézout’s identity and a unimodular integer basis transformation for an integer array \(w\).

Details

Given an integer array \(w = (w_1,\ldots,w_n)\), the function returns integers \(b_i\) (Bézout coefficients) satisfying

\[\sum_{i=1}^{n} b_i \, w_i = \gcd(w_1,\ldots,w_n) \,,\]

together with a unimodular integer matrix \(\Lambda \in \mathrm{GL}(n,\mathbb{Z})\) such that

\[\Lambda \, w = \bigl(\gcd(w_1,\ldots,w_n),\; 0,\;\ldots,\; 0\bigr)^T \,.\]

The algorithm iteratively reduces pairs of entries via the Euclidean algorithm, tracking the accumulated integer row operations in \(\Lambda\). Edge cases (single non-zero entry, all-zero input) are handled explicitly.

Parameters:

w (Union[Array, ndarray, bool, number, bool, int, float, complex]) – Integer input array of length \(n\).

Returns:

• tuple – (Bezout, GCD, Lambda) where

• - ``Bezout`` (np.ndarray, shape (n,), dtype int) – Bézout coefficients satisfying \(\sum_i \text{Bezout}_i \cdot w_i = \gcd(w)\).

• - ``GCD`` (int) – entries of \(w\).

• - ``Lambda`` (np.ndarray, shape (n, n), dtype int) – Unimodular transformation satisfying \(\Lambda w = (\gcd(w), 0,\ldots,0)^T\).

Return type:

Tuple[ndarray, int, ndarray]

See also: orthogonal_lattice(), and the conifold-specific jaxvacua.conifold.conifold_utils.get_basis_change().