An application of the Gröbner basis in computation for the minimal polynomials and inverses of block circulant matrices (Q1611837)

The authors show that the ring \(F[\tau_1,\ldots,\tau_n]\) of all level-\(n(r_1,\ldots,r_n)\)-block circulant matrices over the field \(F\) is isomorphic to \(F[x_1,\ldots,x_n]/<x_1^{k_1}-r_1,\ldots, x_n^{k_n}-r_n>\), where the dimension of the \(i^{th}\) block is \(k_i\) and \(r_i\) is the field element in the lower left corner of the \(i^{th}\) block. They further show that the minimal polynomial of the matrix \(f(\tau_1,\ldots,\tau_n)\) is the monic polynomial that generates the ideal \(<x_1^{k_1}-r_1,\ldots,x_n^{k_n}-r_n,y-f(x_1,\ldots,x_n)> \cap F[y]\), which can be calculated readily using Gröbner basis techniques. A similar formula is given for the annihilation ideal of a set of level-\(n(r_1,\ldots,r_n)\)-block circulant matrices. The authors show that the matrix \(f(\tau_1,\ldots\tau_n)\) is non-singular if and only if \[ 1 \in \langle f(x_1,\dots,x_n),x_1^{k_1}-r_1,\dots,x_n^{k_n}-r_n\rangle,\text{ i.e. }1 = fg + \sum w_i(x_i^{k_i}-r_i). \] They also show how Gröbner basis techniques can be used to calculate \(g\), the inverse of \(f\), explicitly. Finally, the authors give two algorithms, both using Gröbner bases, for the inverse of a level \(n(r_1,\ldots,r_n)\)-block circulant matrix over a quaternion division algebra. All algorithms are explained in detail and have been implemented by the authors in CoCoa 4.0, a computer algebra system.