A Short Proof of the Existence of Vector Euclidean Algorithms
Helaman Rolfe Pratt Ferguson · Proceedings of the American Mathematical Society · 1986
The classical Euclidean algorithm for pairs of real numbers is generalized to real $n$-vectors by ${\text {Alg}}\left ( {n,{\mathbf {Z}}} \right )$. An iteration of ${\text {Alg}}\left ( {n,{\mathbf {Z}}} \right )$ is defined by three steps. Given $n$ real numbers ${\text {Alg}}\left ( {n,{\mathbf {Z}}} \right )$ constructs either $n$ coefficients of a nontrivial integral linear combination which is zero or $n$ independent sets of simultaneous approximations. Either the coefficients will be a column of a ${\text {GL}}\left ( {n,{\mathbf {Z}}} \right )$ matrix or the simultaneous approximations will be rows of ${\text {GL}}\left ( {n,{\mathbf {Z}}} \right )$ matrices constructed by ${\text {Alg}}\left ( {n,{\mathbf {Z}}} \right )$. This algorithm characterizes linear independence of reals over rationals by ${\text {GL}}\left ( {n,{\mathbf {Z}}} \right )$ orbits of rank $n - 1$ matrices.