(i)
If \(\det (G) = C^*\)  then \(G^0\sim (C^*)^n\)  and
\(G\sim (C^*)^n \times \mathbb {Z}/ n \mathbb {Z}\) .

If \(\det (G)=\mathbb {Z}/ \nu \mathbb {Z}\)  then \({G^0\sim (C^*)^{n-1}}\)  and
\(G\sim (C^*)^{n-1} \times \mathbb {Z}/ ns \mathbb {Z}\)  where
\(s = \left\lbrace \begin{array}{ll}\nu /n & \text{ if } \nu \in n\mathbb {N}^* \\\nu & \text{ otherwise. }\end{array}\right.\) 

At the end of this section, we explain how to compute a reduced form and a gauge transformation which gives this reduced form (see Proposition REF ).
Imprimitive groups that may occur
Let us now describe the possible irreducible imprimitive groups that may occur as difference Galois groups when \(n\)  is prime.
For \((\alpha _{1},\dots , \alpha _n)\in (C^*)^n\) , let
\(E_n (\alpha _{1},\dots , \alpha _n):=\begin{pmatrix}& \alpha _1&&\\& &\ddots & \\&&&\alpha _{n-1}\\\alpha _n&&&\end{pmatrix}=\mathrm {Diag} (\alpha _{1},\dots , \alpha _n)E_n, \) 
where
\(E_n=\begin{pmatrix}& 1&&\\& &\ddots & \\&&&1\\1&&&\end{pmatrix}\)  is the companion matrix with last row \((1,0,\dots ,0)\) . To lighten the notations, we will denote it \(E\) . For \((\alpha _{1},\dots , \alpha _n)\in (C^*)^n\) , let \(\bar{\alpha }:=(\alpha _{1},\dots , \alpha _n)\)  and let \(\Pi \bar{\alpha } :=\prod _{i=1}^{n}\alpha _{i}\) . Note that \(\left(E_n (\alpha _{1},\dots , \alpha _n)\right)^n=(\Pi \bar{\alpha } )\mathrm {Id}_n\) . Let \(V_\ell \)  be the set of invertible matrices of the form \(\mathrm {Diag} (\alpha _{1},\dots , \alpha _n)E^{\ell }\) . Note that \(V_0\)  is composed by diagonal matrices. The following theorem lists the possible groups that may occur as Galois groups.
Theorem 3.4 
Assume that \(n\)  is prime. Let \(G \subset \mathrm {GL}_n (C)\)  be an imprimitive irreducible group such that \(G/G^{0}\)  is finite and cyclic. Then, up to a conjugation, one of the following holds:
(i)
 \(G= \displaystyle \bigcup _{\ell =0}^{n-1} V_{\ell }\) . In that case \(G^0\sim (C^*)^n\) ,
\(G\sim (C^*)^n \times \mathbb {Z}/ n \mathbb {Z}\)  and \(\det (G)=C^*\) .

 There exists a positive integer \(s\)  such that
\(G\cap V_0= \left\lbrace \mathrm {Diag}(\alpha _{1},\dots , \alpha _n)\mid (\Pi \overline{\alpha })^{s}=1\right\rbrace \) 
and there exists \(F\)  of the form \(E_n\left(\alpha _{1},\dots , \alpha _n\right)\) , where \(\Pi \overline{\alpha }=e^{2\mathbf {i}\pi k/ns}\)  with \(\gcd (k,s)=1\) , such that \(G/G^0\)  is generated by \(F\) . In that case, we find that
\({G^0= \left\lbrace \mathrm {Diag}(\alpha _{1},\dots , \alpha _n)\mid \Pi \overline{\alpha }=1\right\rbrace \sim (C^*)^{n-1}}\) ,
\(G\sim (C^*)^{n-1} \times \mathbb {Z}/ ns \mathbb {Z}\)  and
(i)
 if \(n=2\)  then \(\det (G)=\mathbb {Z}/ (2s/\gcd (k+s,2)) \mathbb {Z}\) ;

 if \(n> 2\)  then \(\det (G)=\mathbb {Z}/ (ns/\gcd (k,n)) \mathbb {Z}\) .


Up to a conjugation, \(G\)  is a subgroup of \( \displaystyle \bigcup _{\ell =1}^{n} V_{\ell }\) .
Since \(G\)  is irreducible, it contains a non diagonal element thus there exists \(0<\ell <n\)  such that \(G\)  contains an element of \(V_{\ell }\) . Using that \(G\)  is a group, \(G\)  contains an element of \(V_{k\ell }\)  for all \(k\in \mathbb {Z}\) . Since \(n\)  is prime, for all \(0\leqslant k^{\prime }<n\) , there exists an integer \(k\)  such that \(k\ell = k^{\prime } \mod {n}\) . This shows that \(G\)  contains an element of \(V_{k^{\prime }}\) , for all \(0\leqslant k^{\prime } <n\) .
Let \(D\)  be the diagonal elements of \(G\) . It induces an algebraic subgroup of \(n\)  copies of the multiplicative group.
Assume first that \(D\)  is equal to the group of invertible diagonal matrices. Since the latter is connected, \(G^0=D\) .
Thus, \(G\)  contains all the invertible diagonal elements. Since \(G\)  contains an element of \(V_{k^{\prime }}\)  for all \(0\leqslant k^{\prime } <n\)  and contains \(V_0\)  it follows that \(G= \displaystyle \bigcup _{\ell =0}^{n-1} V_{\ell }\) . This is the first case.
Assume now that \(D\)  is strictly included in the group of invertible diagonal matrices. There exists \(\mathbf {s}:=(s_1,\dots s_n)\in \mathbb {Z}^n\) , where the \(s_i\)  are not all zero, such that the diagonal matrices \(\mathrm {Diag}(\alpha _{1},\dots , \alpha _n)\)  in \(G\)  satisfy \(\prod \limits _{j=1}^n \alpha _j^{s_j}=1\) .
We have \(\sum _{j=1}^{n}s_j \arg (\alpha _j)\in 2\mathbf {i}\pi \mathbb {Z}\)  (note that we see the \(\alpha _j\)  in the Riemann surface of the logarithm with argument in \([0,2\pi )\) ) and we want to prove that \(\sum _{j=1}^{n}s_j \arg (\alpha _j)=0\) . Let us define \(\phi \)  to be the continuous map from \(D\)  to \(2\mathbf {i}\pi \mathbb {Z}\)  that sends \(\mathrm {Diag}(\alpha _1, \dots , \alpha _n)\)  to \(\sum _{j=1}^{n}s_j \arg (\alpha _j)\) . Since the identity, which is in \(G^0\) , has image 0 and \(\phi \)  is continuous, we find that \(\phi (G^0)\subset \lbrace 0\rbrace \) . Using the fact that \(G/G^0\)  is finite and cyclic shows that \(\phi (D)\subset \lbrace 0\rbrace \) . Then, \(\sum _{j=1}^{n}s_j \arg (\alpha _j)=0\) . Consider a matrix \(P:=E_n\left(\beta _1,\ldots , \beta _n\right)\in V_1\cap G\, .\) 
We have
\(P .\text{Diag}\left(\alpha _n,\alpha _1,\alpha _{2},\ldots , \alpha _{n-1} \right) = \text{Diag}\left(\alpha _1,\alpha _{2},\ldots , \alpha _{n} \right).P\, .\) 
Therefore, if \(\text{Diag}\left(\alpha _1,\alpha _{2},\ldots , \alpha _{n} \right)\in G\)  then \(\text{Diag}\left(\alpha _n,\alpha _1,\alpha _{2},\ldots , \alpha _{n-1} \right)\in G\) .
Iterating this computation, we obtain that the vector \(X=( \log (\alpha _{1}),\dots , \log (\alpha _{n}))^t\)  is a solution of
\(BX=0, \quad \hbox{ where} \quad B=\begin{pmatrix}s_1&s_2 &\cdots &s_n\\s_n &s_1 &\ddots &\vdots \\\vdots &\ddots & \ddots & s_2\\s_{2}&\cdots & s_n &s_{1}\end{pmatrix}.\) 
Note that \(B= \sum _{\ell =0}^{n-1} s_{\ell +1} E^{\ell }\)  is a circulant matrix. Since \(E^n\)  is the identity, \(E\)  is diagonalisable with eigenvectors \(X_k=(1, e^{2\mathbf {i}k\pi /n}, \dots , e^{2\mathbf {i}k(n-1)\pi /n} )^t\) , \(0\leqslant k\leqslant n-1\) , and its eigenvalues are the \(n\) th roots of unity:
\(EX_k = e^{2\mathbf {i}k\pi /n}X_k\, .\) 
These eigenvectors are also eigenvectors for every polynomial in \(E\) , in particular they are eigenvectors of \(B\) .
Since \(E\)  is diagonalisable, we may write \(E=PD_0 P^{-1}\) , where \(D_0 =\mathrm {Diag}(1,e^{2\mathbf {i}\pi /n},\dots ,e^{2\mathbf {i}(n-1)\pi /n})\)  is a diagonal matrix.
Since \(BX=0\) , and \(P^{-1}BP=\sum _{\ell =0}^{n-1} s_{\ell +1} D_0^{\ell }\) , the right-hand side of this diagonal matrix has a nontrivial kernel. Therefore, there exists \(0\leqslant k_0 \leqslant n-1\)  such that \(\sum _{\ell =0}^{n-1} s_{\ell +1} e^{2\mathbf {i}\ell k_0\pi /n}=0\) .
The \(n\) th roots of unity satisfy \(X^n=1\)  and we have \(X^n -1=(X-1)\Phi _n(X)\)  where \(\Phi _n(X):=1+X+\dots +X^{n-1}\) . Because \(n\)  is prime, the cyclotomic polynomial \(\Phi _n\)  is irreducible on \(\mathbb {Z}\) . If \(k_0>0\) , then we must have \(s:=s_1=\dots =s_n\ne 0\) . Let us prove by contradiction that we work in the case \(k_0\ne 0\) .
By contradiction, assume that \(k_0=0\) . Then, \(\sum _{\ell =0}^{n-1} s_{\ell +1}=0\) . Recall that the \(s_i\)  are not all zero. In particular, we cannot be in the situation where \(s_1=\dots =s_n\) .
From what precedes, this implies that for all \(k\ne 0\)  we have \(X_k\notin \ker (B)\) . Thus, \(\ker (B)=\mathrm {Vect}(X_0)\)  and in particular \(X\in \mathrm {Vect}(X_0)\)  that is \(\log (\alpha _{1})=\dots =\log (\alpha _{n})\) . We obtain that all diagonal elements of \(G\)  are homotecy so the connected component \(G^0\)  commutes with all elements of \(G\) . Since \(G/G^0\)  is finite cyclic, it is generated by a matrix \(F\) . So \(G=G^0\cup G^0 F \cup \dots \cup G^0 F^{m-1}\)  for some integer \(m\) . The matrix \(F\)  is trigonalisable and since \(G^0\)  is formed by homotecy, it implies that there is a common basis of trigonalisation of every elements of \(G\) , which contradicts the fact that \(G\)  is irreducible. Therefore, \(k_0>0\)  so we must have \(s:=s_1=\dots =s_n\ne 0\) .
We proved that \(D\subset D_s:=\lbrace \mathrm {Diag}(\alpha _{1},\dots , \alpha _n)\mid (\Pi \overline{\alpha })^{s}=1\rbrace \)  and, since \(D_{s}=D_{-s}\) , we can assume that \(s\)  is positive. If \(D\)  is a strict subgroup of \(D_s\) , the same reasoning implies that \(D\subset D_{s^{\prime }}\)  for some \(s^{\prime }\)  that divides \(s\) . So, up to taking a smaller positive integer \(s\) , we may assume that \(D= D_s\) .
In this case, \(G^0=D_1\) .
Let \(F:=\mathrm {Diag} (\alpha _{1},\dots , \alpha _n)E^{\ell }\in V_{\ell }\cap G\)  be a non diagonal element of \(G\)  which generates the finite group \(G/G^0\)  (we can choose in particular \(0<\ell <n\) ). Since \(n\)  is prime, \(n\)  is the smallest integer such that \(F^n\)  is diagonal. We have \(F^n = \mathrm {Diag} (\Pi \bar{\alpha },\dots , \Pi \bar{\alpha })\)  thus it satisfies \((\Pi \bar{\alpha })^{sn}=1\) . We have \(\Pi \bar{\alpha }=e^{2\mathbf {i}\pi k/sn}\)  for some integer \(0\leqslant k<sn\)  and \(F^n\)  has to generate the diagonal elements of \(G/G^0\) . This shows that \((\Pi \bar{\alpha })^n\)  has to be a primitive \(s\) th root of unity, that is, \(k\)  has to be coprime with \(s\) . Since \(G\)  is defined up to an isomorphism and since \(F\)  is conjugate to \(\mathrm {Diag} (\alpha _{\mu (1)},\dots , \alpha _{\mu (n)})E\)  where \(\mu \in \mathfrak {S}_n\)  is a permutation, we can assume (up to renumbering the \(\alpha _i\) 's, which can be done since we just have conditions on \(\Pi \bar{\alpha }\) ) that \(F = \mathrm {Diag} (\alpha _{1},\dots , \alpha _n)E = E_n\left(\alpha _{1},\dots , \alpha _n\right)\) .
The determinant of the diagonal elements is a power of \(e^{2\mathbf {i}\pi /s}\) . When \(n>2\) , \(n\)  is odd and the determinant of \(F\)  is \(e^{2\mathbf {i}\pi k/sn}\) . When \(n=2\)  the determinant of \(F\)  is \(-e^{2\mathbf {i}\pi k/2s}=e^{2\mathbf {i}\pi (k+s)/2s}\) .
The results on the determinant follow.
Remark 3.5 When \(n=2\) , we recover [1]}.

Let us now see how \(\det (G)\)  helps us to distinguish the cases in Theorem REF  and compute \(s\) . We will explain how to compute \(\det (G)\)  in Section REF .
Proposition 3.6 
Assume that \(n\)  is prime. Let \(G \subset \mathrm {GL}_n (C)\)  be an imprimitive irreducible group such that \(G/G^{0}\)  is finite and cyclic. The following statements holds.

\(\det (G)=C^*\)  if and only if \(G\)  is the group in the case REF  of Theorem REF .

If \(\det (G)=\mathbb {Z}/ \nu \mathbb {Z}\) , with \(\nu \in n\mathbb {N}^*\) , then \(s=\nu /n\) . where \(s\)  is defined in Theorem REF .

Otherwise, \(s=\nu \) .


If \(\det (G)=C^*\)  we are clearly in the case case REF  of Theorem REF . The converse is also true.
Assume that \(n\ne 2\) , thus by Theorem REF , \(\det (G)=\mathbb {Z}/ (sn/\gcd (k,n)) \mathbb {Z}\) . We know the integers \(n\) , \(\nu :=(sn/\gcd (k,n))\)  and we want to compute \(s\) .
Note that, since \(n\)  is prime, \(\nu =sn/\gcd (k,n)\)  is either \(sn\)  or \(s\) . Let us prove that \(\nu =s\)  if and only if \(\gcd (\nu ,n)=1\) . If \(\nu =s\)  then \(\gcd (k,n)=n\)  and, since \(k\)  is coprime with \(s\) , this implies \(\gcd (n,s)=1\) , that is \(\gcd (\nu ,n)=1\) . Obviously, if \(\nu =sn\)  then \(\gcd (\nu ,n)=n\) .
Therefore, either \(\gcd (\nu ,n)=1\)  and \(s=\nu \)  either \(\gcd (\nu ,n)=n\)  and \(s=\nu /n\) .
In the case \(n=2\) , \(k\)  is replaced by \(k+s\) . Note that \(k+s\)  is coprime with \(s\)  and the same conclusion holds.

How to compute a reduced form?
The rest of the subsection is devoted to the computation of the reduced form.
We recall that \(A_{[\ell ]}:=\phi ^{\ell -1}(A)\dots A\)  and \(G_{[\ell ]}\)  is the difference Galois group of the system \(\phi ^{\ell }(Y)=A_{[\ell ]}Y\) . Let us first give a criterion of imprimitivity.
Proposition 3.7 
Assume that \(G\)  is irreducible and \(n\)  prime. It is imprimitive if and only if \(G_{[n]}\)  is diagonal.
Furthermore, when \(G\)  is imprimitive, the Riccati equation corresponding to \(\phi ^n (Y)=A_{[n]}Y\)  admits a solution \(d\in \mathbf {k}^*\)  and we may assume that the \((1,1)\)  entry of \(A_{[n]}\)  is \(d\) .

If \(G\)  is imprimitive but irreducible, there exists a gauge transformation \(T\)  such that \(B:=\phi (T)AT^{-1}\)  is an invertible matrix of the form \(\begin{pmatrix}& b_1&&\\& &\ddots & \\&&&b_{n-1}\\b_{n}&&&\end{pmatrix}\) , where \(b_i\in \mathbf {k}^*\) , and such that \([B]\)  is in reduced form. Then, \(\phi ^{n}(T)A_{[n]}T^{-1}=\phi ^{n-1}(B)\dots \phi (B)B=:B_{[n]}\)  is diagonal. By Theorem REF ,
this proves that the Galois group of \(\phi ^{n}(Y)=A_{[n]}Y\)  is diagonal.
Let us prove the converse. Assume that the Galois group of \(\phi ^{n}(Y)=A_{[n]}Y\)  is diagonal, and \(G\)  is irreducible. Then, from Lemma REF , \(G^0\)  is diagonal. Let us prove that \(G\)  is imprimitive.
Let \(V_1,\dots ,V_k\)  be invariant subspaces of \(G^0\) . The direct sum of the \(V_i\)  is \(C^n\) . Let \(g\in G\) . We have \(gG^0= G^{0} g\)  because \(G^0\)  is a normal subgroup of \(G\) . In particular, \(gG^0 (V_i)= G^{0} g(V_i)\) , showing that for all \(h\in G^0\) , \(g(V_i)=hg(V_i)\) . Then, there exists \(j\)  such that \(g(V_i)=V_j\)  proving that \(G\)  is imprimitive.
The statement on the Riccati equation is a consequence of the results of Section REF .
Remark 3.8 When \(n\)  is not necessarily prime, we find that \(G_{[n]}\)  is bloc diagonal with blocs of same size, denoted by \(\ell \)  where \(\ell \)  is a divisor of \(n\) . In that case \(n/\ell \)  is equal to the number of proper \(C\) -spaces permuted by \(G\) .

Assume that \(G\)  is irreducible, imprimitive and \(n\)  is prime. By Proposition REF , the Riccati equation corresponding to \(\phi ^n (Y)=A_{[n]}Y\)  admits a solution \(d\in \mathbf {k}^*\) . Assume that we are able to compute a reduced form of \(\phi (y)=dy\) , that is compute \(f\in \mathbf {k}^*\)  such that \(\phi (y)=d\frac{\phi (f)}{f}y\)  is reduced. The goal of what follows is to prove the following result.
Proposition 3.9 
The system \(\phi (Y)=AY\)  is equivalent to \(\phi (Y)=E_n (1,\dots , 1, d)Y\) .
The system \(\phi (Y)=E_n (1,\dots , 1,f^{-1}, \phi (f)d)Y\)  is a reduced form of \(\phi (Y)=E_n (1,\dots , 1, d)Y\)  with reduction matrix \(\mathrm {Diag}(1,\ldots ,1,f)\) .

Let us begin by proving a technical lemma.
Lemma 3.10 
Assume that \(G\)  is irreducible and imprimitive. Then, there exists \(T\in \mathrm {GL}_n (\mathbf {k})\)  and \(u\in \mathbf {k}^*\)  such that \(\phi (T)AT^{-1}=\begin{pmatrix}& 1&&\\& &\ddots & \\&&&1\\u&&&\end{pmatrix}\) , that is, \(\phi (T)AT^{-1}=E_n(1,\ldots ,1,u)\) .

This is inspired by [1]}. By Theorem REF , there exist \(T\in \mathrm {GL}_n (\mathbf {k})\)  and \(u_1,\dots , u_n \in \mathbf {k}^*\)  such that
\(\phi (T)AT^{-1}=E_n(u_2,\ldots ,u_n,u_1)\) .
Let \(D:=\mathrm {Diag}\left(a_1,\ldots ,a_n\right)\) .
We have the following equality
\(\phi (D)E_n(u_2,\ldots ,u_n,u_1)D^{-1} = E_n\left(\frac{\phi (a_1) u_2}{a_2},\ldots ,\frac{\phi (a_{n-1}) u_n}{a_n},\frac{\phi (a_n) u_1}{a_1}\right)\, .\) 
If we perform the gauge transformation \(D:=\mathrm {Diag}(1,u_2,1,\ldots ,1)\) , we may reduce to the case \(u_2=1\) . Then, if \(n>2\) , performing the gauge transformation \(D:=\mathrm {Diag}(1,1,\phi (u_2)u_3,1,\ldots ,1)\) , we may reduce to the case \(u_3=1\) . Iterating this process allows at the end to reduce to the case \(u_2= \dots =u_n=1\)  and we change \(u_1\)  in \(u:=u_1\phi (u_n)\phi ^2(u_{n-1})\ldots \phi ^{n-1}(u_2)\) .
Let us continue the proof of Propositon REF .
By the previous lemma, we have that \([A]\)  is equivalent to \(E_n(1,\ldots ,1,u)\) , therefore \(\phi ^n(Y)=A_{[n]}Y\)  is equivalent to \(\phi ^n(Y)=\mathrm {Diag}(u,\phi (u),\dots , \phi ^{n-1} u)Y\) . Unfortunately, we are not yet able to compute \(u\) . By Proposition REF , there exists
a diagonal system \(\phi ^n (Y)=DY\) , that is equivalent to \(\phi ^n (Y)=A_{[n]}Y\)  with \((1,1)\)  entry \(d\) .
We write
\(D:=\mathrm {Diag}(d_1,d_2,d_3,\ldots ,d_n)\) 
where we set \(d_1:=d\) . Let us now see that we may reduce to the case where \(d_i=\phi ^{i-1}(d_1)\) .
Lemma 3.11 There exists a diagonal gauge transformation \(X\)  such that
\(\phi ^n (X)DX^{-1}= \mathrm {Diag}(d,\phi (d),\dots , \phi ^{n-1} (d))\, .\) 

Note that there exists an invertible matrix \(Z\)  such that \(\phi ^n (Z)DZ^{-1}=\mathrm {Diag}(u,\phi (u),\dots , \phi ^{n-1} u)\) . Since the right-hand side and \(D\)  are diagonal, there is an invertible diagonal matrix \(Y\)  such that
\(\phi ^n (Y)DY^{-1}=\mathrm {Diag}(u,\phi (u),\dots , \phi ^{n-1} u)\) . More precisely, using that \(\phi ^n (Z)D=\mathrm {Diag}(u,\phi (u),\dots , \phi ^{n-1} u)Z\) , we can choose the entries of the diagonal matrix \(Y\)  to be the entries in the main diagonal of \(Z\) .
Let \(y_i\)  be the \((i,i)\)  entry of \(Y\) .
Since \(\phi ^n(Y)DY^{-1}=\mathrm {Diag}(u,\phi (u),\dots , \phi ^{n-1} u)\) , we have \(\phi ^n(y_1)d_1/y_1=u\) . Then, \(\phi ^{n+i-1} (y_1)\phi ^{i-1}(d)/\phi ^{i-1}(y_1)=\phi ^{i-1}(u)\)  and therefore if we let \(Y_0= \mathrm {Diag}(1/y_1 ,\dots , 1/\phi ^{n-1}(y_1) )\) , we find
\(\phi ^n (Y_0Y)D(Y_0 Y)^{-1}=\mathrm {Diag}(d,\phi (d),\dots , \phi ^{n-1} (d))\) . This proves the existence of \(X\) .
Thus, at this stage, we know that \(\phi ^n (Y)=A_{[n]}Y\)  is equivalent to
\(\phi ^n(Y)=\mathrm {Diag}(d,\phi (d),\ldots , \phi ^{n-1}(d))Y\, .\) 
Since the system \(\phi ^n (Y)=\mathrm {Diag}(d,\phi (d),\dots , \phi ^{n-1}(d))Y\)  is diagonal, we may assume that we have a diagonal fundamental matrix of solutions \(U\) . This matrix can be taken of the form \(U=\mathrm {Diag}(y,\phi (y),\dots , \phi ^{n-1} y)\) . Then,
\(\phi (U)=FU, \quad \text{where}\quad F:=\begin{pmatrix}& 1&&\\& &\ddots & \\&&&1 \\d&&&\end{pmatrix}=E_n (1,\dots , 1, d)\, .\) 
By construction, \(F_{[n]} = \mathrm {Diag}(d,\phi (d),\ldots ,\phi ^{n-1}(d))\) . We thus have two \(\phi ^n\) - systems that are equivalent and we want to prove that they are equivalent as \(\phi \) -system. This is the goal of the next lemma.
Lemma 3.12 
Let \(B\in \mathrm {GL}_n(\mathbf {k})\)  be such that the systems \(\phi ^n(Y) = B_{[n]}Y\)  and \(\phi ^n(Y) = A_{[n]}Y\)  are equivalent.
Then, the systems \([A]\)  and \([B]\)  are equivalent.

Let \(\mathcal {Y}\)  and \(\mathcal {Z}\)  be two fundamental matrices of solutions of \(\phi (Y)=AY\)  and \(\phi (Y)=BY\)  respectively.
Thus, \(\phi ^n(\mathcal {Y})=A_{[n]}\mathcal {Y}\)  and \(\phi ^n(\mathcal {Z})=B_{[n]}\mathcal {Z}\) . By hypothesis, there exists \(T\in \mathrm {GL}_n(\mathbf {k})\)  such that \(\mathcal {X}:=T\mathcal {Y}\)  is a solution of \(\phi ^n(Y)=B_{[n]}Y\) .
This implies that \(P:=\mathcal {X}^{-1}\mathcal {Z}\)  is a \(\phi ^n\) -constant matrix. By [3]}, the entries of \(P\)  belong to \(C\)  so we have
\(A = \phi (\mathcal {Y})\mathcal {Y}^{-1} = \phi (T^{-1}) \phi (\mathcal {X})\mathcal {X}^{-1}T= \phi (T^{-1}) \phi (\mathcal {Z})\mathcal {Z}^{-1} T =\phi (T)^{-1} BT .\) 
Let us finish the proof of Proposition REF . From what precedes, \([A]\)  is equivalent to \([F]\)  where \(F=E_n (1,\dots , 1, d)\) . Now, we perform the gauge transformation \(S=\mathrm {Diag}(1,\ldots ,1,f)\)  to find that \([A]\)  is equivalent to \(\phi (Y)=E_n (1,\dots , 1,f^{-1}, d\phi (f))Y\) . It remains to check that this system is in a reduced form.
By Theorem REF , there exists a reduction matrix of the form
\(T:= \mathrm {Diag}(f_1,\dots , f_n)E^k\) . Note that \(T\)  may be the identity. Then, the product of the nonzero entry of \(B:=\phi (T)E_n (1,\dots , 1,f^{-1}, d\phi (f))T^{-1}\)  is \(\frac{\phi (f_1\times \dots \times f_n) }{f_1\times \dots \times f_n}\frac{\phi (f)}{f}d\) . Since \(\phi y=\frac{\phi (f)}{f}dy\)  is in reduced form, the algebraic group generated by \(\frac{\phi (f_1\times \dots \times f_n) }{f_1\times \dots \times f_n}\frac{\phi (f)}{f}d\)  is bigger than the algebraic group generated by \(\frac{\phi (f)}{f}d\) . Since \([B]\)  is reduced, by Theorem REF , it is also smaller, proving that the algebraic group generated by \(\frac{\phi (f_1\times \dots \times f_n) }{f_1\times \dots \times f_n}\frac{\phi (f)}{f}d\)  is the algebraic group generated by \(\frac{\phi (f)}{f}d\) . By Theorem REF  again, this shows that \(\phi (Y)=E_n (1,\dots , 1,f^{-1}, d\phi (f))Y\)  is already reduced.
Example 3.13 
Let us go back to the example (REF ) and recall, see Example REF , that the difference Galois group \(G\)  is ireducible. Assume that \(t\ne 0\) . Instead of applying the criterion of Proposition REF  to show that \(G\)  is imprimitive, let us use a shortpath. We refer to [4]} for more details on what follows.
We define the Newton polygon of a \(q\) -difference operator
\(L=\sum _i a_{i} \phi ^k\) 
as the convex hull in \(\mathbb {R}^2\)  of
\(\lbrace (i,j) \ \vert \ i,j \in \mathbb {Z}, \ j \geqslant \operatorname{val}(a_{i}(z))\rbrace  \subset \mathbb {R}^{2}\) 
where \(\operatorname{val}: \mathbb {C}((z)) \rightarrow \mathbb {Q}\cup \lbrace +\infty \rbrace \)  denotes the \(z\) -adic valuation. The Newton polygon is invariant by an analytic change of variables.
By Lemma REF , when \(n\)  is prime, if the difference Galois group of an equation is irreducible and imprimitive, then the lower bound of the Newton polygon is delimited by the segment from \((0,\operatorname{val}(u))\)  to \((n,0)\) . In Example (REF ), the lower part is composed by the segment delimited by \((0,1)\)  and \((1,0)\)  and the segment delimited by \((1,0)\)  and \((3,0)\) , see Figure REF . Since \(G\)  is irreducible, see Example REF , we find that \(G\)  is primitive.
<FIGURE>
Galois groups of equations of order one and diagonal systems
Galois groups of equations of order one
We consider the equation of order one
\(\phi (y)=\alpha y \, .\) 
Let us now see how to compute the Galois group \(G\)  of this difference equation. Recall that since \(G\subset \mathrm {GL}_1 (C)\)  is an algebraic group, either \(G\)  is \(C^*\) , either it is isomorphic to \(\mathbb {Z}/\ell \mathbb {Z}\)  for some \(\ell \in \mathbb {N}^*\) .
Proposition 4.1 
We have \(G\sim \mathbb {Z}/\ell \mathbb {Z}\)  if and only if there exists \(\zeta \) , a primitive \(\ell \) th root of unity and a nonzero solution \(f\in \mathbf {k}^*\)  of \(\phi (y)=(\zeta /\alpha )y\) . In that situation, \(\zeta =\alpha \frac{\phi (f)}{f}\) , and \([\zeta ]\)  is a reduced form of \([\alpha ]\)  with a gauge transformation \((f)\) .

Since the Galois group \(G\)  of (REF ) is an algebraic subgroup of \(C^{\star }\) , it is a finite cyclic group or the multiplicative group \(C^{\star }\) .
Any equivalent equation of (REF ) is of the form \(\phi (y)=\alpha \frac{\phi (f)}{f}y\)  with \(f\in \mathbf {k}^{\star }\) .
Therefore, from Theorem REF , if \(G\)  is a finite cyclic group of order \(\ell \in \mathbb {N}^\star \)  then there exist \(f\in \mathbf {k}^{\star }\)  and \(\zeta \) , a primitive \(\ell \) th root of unity, such that \(\zeta = \alpha \frac{\phi (f)}{f}\) .
Conversely, assume that there exist \(f\in \mathbf {k}^{\star }\)  and \(\zeta \) , a primitive \(\ell \) th root of unity, such that \(\zeta = \alpha \frac{\phi (f)}{f}\) . From Theorem REF , \(G\)  is contained in \(\mathbb {Z}/\ell \mathbb {Z}\) . Then,
\(G\sim \mathbb {Z}/\ell _1\mathbb {Z}\)  where \(\ell _1\)  divides \(\ell \) . Then, there exist \(g\in \mathbf {k}^{\star }\)  and \(\zeta _1\) , a primitive \(\ell _1\) th root of unity, such that \(\zeta _1= \alpha \frac{\phi (g)}{g}\) . This implies \(\alpha ^{\ell _1}=g^{\ell _1}/\phi (g^{\ell _1})\) . Let \(h:=(f/g)^{\ell }\) . Thus, \(\phi (h) = h\)  so \(h\in C^\star \) . Since \(C\)  is algebraically closed, there exists \(c\in C\)  such that \(f=cg\)  (with \(c^{\ell } = h\) ). Using this equality, we obtain \(\zeta = \zeta _1\)  and since \(\zeta \)  is a primitive \(\ell \) th root of unity, \(\ell =\ell _1\) .
Remark 4.2 Since \(\det (G)\)  is the Galois group of \(\phi (y)=\det (A)y\) , an equation of order 1, we may now compute \(\det (G)\)  if we are able to reduce the difference equations of order 1.

Example 4.3 
Consider the difference equation (REF ) and let \(G\)  be its difference Galois group over \(\mathbb {C}(z^{1/*})\) . Assume that \(t\ne 0\) . We want to compute \(\det (G)\) . We have to compute the difference Galois group of \(\det (y)=\frac{-q^3 z}{t}y=\alpha y\)  over \(\mathbb {C}(z^{1/*})\) . By Proposition REF , \(\det (G)\)  is finite if and only if there exists \(\zeta \) , a primitive \(\ell \) th root of unity, and a nonzero solution \(f\in \mathbf {k}^*\)  of \(\phi (y)=(\zeta /\alpha )y\) . But the valuation of \(\alpha \)  at \(z=0\)  is 1, proving that \(\zeta /\alpha \)  must have valuation \(-1\) . Since for \(f\in \mathbf {k}^*\) , \(f\)  and \(\phi (f)\)  have the same valuation, the equation \(\phi (f)=(\zeta /\alpha )f\)  with \(f\in \mathbf {k}^*\) , and \(\zeta \)  a root of unity, has no solutions. Therefore, \(\det (G)=\mathbb {C}^*\) .


Galois groups of diagonal systems
For more details on what follows, we refer to [5]}.
Let us consider a diagonal system
\(\phi (Y)=\mathrm {Diag}\left(\alpha _1,\ldots ,\alpha _n\right) Y\) 
where \(\mathrm {Diag}\left(\alpha _1,\ldots ,\alpha _n\right)\in \mathrm {GL}_n\left(\mathbf {k}\right)\)  is the diagonal matrix whose nonzero entry at the line \(i\)  is \(\alpha _i\) .
By Theorem REF , the Galois group is an algebraic subgroup of the \(n\) -dimensional torus \(T\) . The matrices of \(G\)  are of the form \(\mathrm {Diag} (c_1, \dots , c_n)\) . We recall that a character on \(T\)  is a morphism \(\chi :T\rightarrow C^{\star }\) . It is of the form \(\chi _{\mathbf {m}}(x_1,\ldots ,x_n)=x_1^{m_1}\ldots x_n^{m_n}\)  with \(\mathbf {m}:=\left(m_1,\ldots ,m_n\right)\in \mathbb {Z}^n\) . Since an algebraic subgroup of \(T\)  is the intersection of the kernels of some characters on \(T\) , we have to find the \(\mathbf {m}\in \mathbb {Z}^n\)  such that \(c_1^{m_1}\ldots c_n^{m_n}=1\)  for all \(\mathrm {Diag} (c_1, \dots , c_n) \in G\) .
By Theorem REF , a gauge transformation which reduces the system will be diagonal, denoted by \(\mathrm {Diag}(f_1,\dots ,f_n)\) . Thus, the difference Galois group of (REF ) is the intersection of the kernels of the \(\chi _{\mathbf {m}}\)  for all \(\mathbf {m}\in \mathbb {Z}^n\)  such that there exist \(f_1,\ldots , f_n\in \mathbf {k}^\star \)  satisfying
\(\left(\frac{\phi (f_1)}{f_1}\alpha _1 \right)^{m_{1}}\times \ldots \times \left(\frac{\phi (f_n)}{f_n} \alpha _n \right)^{m_{n}}= 1\,.\) 
The question of how to solve (REF ) depends on the examples (see one example in [5]}). In general it is a complicated task.

Galois groups of equations of order two
Consider a difference equation of order 2
\( \phi ^2 (y)+a_1 \phi (y)+a_0 y=0, \quad \text{where}\quad a_i\in \mathbf {k}\quad \text{and}\quad a_0 \ne 0.\) 
Let
\(L := \phi ^2 +a_1 \phi +a_0\in \mathbf {k}\left< \phi ,\phi ^{-1}\right>\) 
be the corresponding difference operator and let \(G\subset \mathrm {GL}_{2}(C)\)  be its Galois group. We want to compute \(G\) . An algorithm in the cases (Q), (S), (E), (M) is presented in [7]}, [1]}, [9]}, [10]} respectively.
Reducible case
We first decide whether \(L\)  has a right factor of order one. This is the case if and only if \(G\)  is reducible. Recall, see Lemma REF , that is is equivalent to the existence of a solution \(\alpha \)  of the Riccati equation \(\phi (y)y+a_1y+a_0=0\) .
Assume first that \(L\)  is reducible and let us write \(L=(\phi -\beta )(\phi -\alpha )\) . Then, \(\alpha \)  is a solution of the Riccati equation \(\phi (y)y+a_1y+a_0=0\) , and \(\beta \)  is determined by \(\alpha \beta =a_0\) . The difference equation is equivalent to \(\phi (Y)=AY\)  where \(A=\left(\begin{array}{cc}\alpha & 1\\0 & \beta \end{array}\right)\) .
We now follow the strategy of Section REF . As in the diagonal case, we reduce the diagonal system \(\phi (Y)=\left(\begin{array}{cc}\alpha & 0\\0 & \beta \end{array}\right)Y\)  with a diagonal matrix \(D\) . Let \(B:=\phi (D)AD^{-1}\) , with \(B=\left(\begin{array}{cc}\alpha ^{\prime } & \gamma ^{\prime }\\0 & \beta ^{\prime }\end{array}\right)\) . By [1]}, either \([B]\)  is already reduced, either a reduced form is \(\left( \begin{array}{cc}\alpha ^{\prime } & 0\\0 & \beta ^{\prime }\end{array}\right)\) .
We now have to decide if there exists \(t\in \mathbf {k}\)  such that \(T=\left(\begin{array}{cc}1 & t\\0 & 1\end{array}\right)\)  satisfies \(\phi (T)B=\left( \begin{array}{cc}\alpha ^{\prime } & 0\\0 & \beta ^{\prime }\end{array}\right)T\) . Note that this is equivalent to
\( \gamma ^{\prime }+ \phi (t) \beta ^{\prime }= \alpha ^{\prime } t.\) 
So we just have to decide if an equation of order 1 has a solution \(t\)  in \(\mathbf {k}\)  or not.
If such a \(t\)  exists, then the reduction matrix is given by \(TD\) , and a reduced form is \(\left( \begin{array}{cc}\alpha ^{\prime } & 0\\0 & \beta ^{\prime }\end{array}\right)\) . Otherwise, the reduction matrix is given by \(D\)  and a reduced form is \(\left(\begin{array}{cc}\alpha ^{\prime } & \gamma ^{\prime }\\0 & \beta ^{\prime }\end{array}\right)\) .

Imprimitive case
Assume now that \(G\)  is irreducible. It is imprimitive if and only if the difference Galois group of \(\phi ^2 Y=A_{[2]}Y\)  is diagonal. We use the reducible case (with \(\phi \)  replaced by \(\phi ^2\) ) to check this property. In that case we are able to compute \(d\in \mathbf {k}^*\) , solution of the Riccati equation corresponding to \(\phi ^2 Y=A_{[2]}Y\) . We now follow Proposition REF . The system \([A]\)  is equivalent to \(\phi Y=\left( \begin{array}{cc}0 & 1\\d & 0\end{array}\right) Y\) .
Let us compute a reduced form of \(\phi (y)=dy\) , that is compute \(f\in \mathbf {k}^*\)  such that \(\phi (y)=d\frac{\phi (f)}{f}y\)  is reduced. Then, a reduced form is given by
\(\left( \begin{array}{cc}0 & f^{-1}\\\phi (f)d & 0\end{array}\right) \)  and a reduction matrix is given by \(\mathrm {Diag}(1,f)\)  .

Primitive case
Assume that \(G\)  is irreducible and primitive. By [12]},
\(G = \lbrace M\in \mathrm {GL}_2\left(\mathbb {C}\right) \mid \det (M)\in \det (G) \rbrace .\) 
In particular, \(G\)  is isomorphic to \(\det (G)\times \operatorname{SL}_2\left(\mathbb {C}\right)\) , via the group morphism defined by \(M\mapsto \left(\det (M),\left( \begin{array}{cc}\det (M)^{-1} & 0\\0& 1\end{array}\right)\times M \right)\) .
Recall that \(a_0=\det (A)\)  and the algebraic group \(\det (G)\)  is the difference Galois group of \(\phi (y)=a_0 y\) , a system of order 1. Let \(f\in \mathbf {k}^*\)  be such that \(\phi (y)=a_0\frac{\phi (f)}{f}y\)  is reduced with Galois group \(\det (G)\) .
Then, we perform, as in [1]}, the gauge transformation \(T=\mathrm {Diag}(f,1)\)  to obtain a system \([B]\) . Since \(\det (B)=a_0\frac{\phi (f)}{f}\) , and \(\phi (y)=a_0\frac{\phi (f)}{f}y\)  is reduced with Galois group \(\det (G)\) , we find that \(B\in G(\mathbf {k})\) . Then, \(B\)  is a reduced form and \(T\)  is the reduction matrix.

Galois groups of equations of order three
Consider a linear difference equation of order 3
\( \phi ^3 (y)+ a_2 \phi ^2 (y)+a_1 \phi (y)+a_0 y=0, \quad \text{where}\quad a_i\in \mathbf {k}\quad \text{and}\quad a_0 \ne 0.\) 
Let
\(L := \phi ^3 + a_2 \phi ^2 +a_1 \phi +a_0\in \mathbf {k}\left< \phi ,\phi ^{-1}\right>\) 
be the corresponding difference operator and let \(G\subset \mathrm {GL}_{3}(C)\)  be its Galois group. We want to compute \(G\) .
Reducible case
We follow the strategy explained in Section REF  to treat the case where \(G\)  is reducible. By [14]}, \(G\)  is reducible if and only if the operator \(L\)  admits a right factor. The right factor can have order one or two. So \(G\)  is reducible if and only if the operator admits a right or left factor of order one. Recall that up to consider the dual, we may reduce to the case where there is a right factor of order 1.
Recall, see Lemma REF , that the existence of a right factor of order one is equivalent to the existence of a solution \(\alpha \in \mathbf {k}\)  of the Riccati equation \(\phi ^2 (y)\phi (y)y+a_2 \phi (y)y+a_1y+a_0=0\) .
Assume that \(L\)  admits a right factor of order one. Let us write \(L\)  as
\(\widetilde{L}(\phi -\alpha )\)  where \(\widetilde{L}:=\phi ^2-\beta \phi -\gamma \) .
Then, the system \([A_L]\)  is equivalent to the system
\(\phi (Y)= \left(\begin{array}{c|c}\alpha & 1 \hspace*{8.5359pt} 0 \\\hline 0 & A_2\end{array}\right)Y \, , \) 
where the matrix \(A_2\)  corresponds to the equation of order two \(\widetilde{L}\)  (that is \(A_2 = A_{\widetilde{L}}\) ).
From the order one and order two cases, we know how to compute \(T_1\in \mathrm {GL}_1 (\mathbf {k})\)  and \(T_2\in \mathrm {GL}_2 (\mathbf {k})\)  such that the systems whose matrices are \(\phi (T_1)\alpha T_1^{-1}\)  and \(\phi (T_2)A_2 T_2^{-1}\)  are in reduced form. Let us consider
\(A := \begin{pmatrix}\phi (T_1)&0 \\0 &\phi (T_2)\end{pmatrix}\left(\begin{array}{c|c}\alpha & 1 \hspace*{8.5359pt} 0 \\\hline 0 & A_2\end{array}\right)\begin{pmatrix}T_1&0 \\0 &T_2\end{pmatrix}^{-1}.\) 
This matrix \(A\)  is of the form
\(\begin{pmatrix}\phi (T_1)\alpha T_1^{-1}&\star \\0 &\phi (T_2)A_2 T_2^{-1}\end{pmatrix}\) .
The first step consists in reducing the bloc diagonal system \([D]\)  where \(D:=\begin{pmatrix}\phi (T_1)\alpha T_1^{-1}&0 \\0 &\phi (T_2)A_2 T_2^{-1}\end{pmatrix}\) . Let \(G_d\)  be the Galois group of this system, let \(G_1\)  be the Galois group of \([\phi (T_1)\alpha T_1^{-1}]\)  and let \(G_2\)  be the Galois group of \([\phi (T_2)A_2 T_2^{-1}]\) .
The algebraic group \(G_d\)  is an algebraic subgroup of \(G_1\times G_2\) . We explain the reduction on a case-by-case approach with respect to \(G_2\) . We will see that in each situation, reducing \([D]\)  is equivalent to reducing a diagonal system whose reduction is explained in Section REF . Let us summarize here the results we are going to prove.
Theorem 6.1 \(\bullet \)  Assume that \(G_2\)  is composed by diagonal matrices. We can assume that \(D\)  is diagonal. Then, we have to reduce a diagonal system and the reduction is explained in Section REF .
\(\bullet \)  Assume that \(G_2\)  is reducible and the first case does not hold. We can assume that \(D\)  is upper triangular. Then, the reduction matrix is the diagonal matrix \(T\)  that reduces the diagonal system \([\mathrm {Diag}(a,b,d)]\) , where \(a,b,d\)  are the diagonal entries of \(D\) .
\(\bullet \)  Assume that \(G_2\)  is imprimitive and irreducible. We can assume that \(\phi (T_2)A_2 T_2^{-1}\)  is an anti-diagonal matrix. Then \(D_{[2]}\)  is diagonal. The reduction matrix that reduces \([D]\)  is the matrix \(T\)  that reduces the diagonal \(\phi ^{2}\) -system \(\phi ^2 Y=D_{[2]}Y\) .
\(\bullet \)  Assume that \(G_2\)  is primitive and irreducible. The reduction matrix is given by \(T:=\mathrm {Diag}(r_1,r_2,1)\) , where \(\mathrm {Diag}(r_1,r_2)\)  is the reduction matrix of the diagonal system \(\phi Y=\begin{pmatrix}\phi (T_1)\alpha T_1^{-1}&0\\0 &\det (\phi (T_2)A_2 T_2^{-1})\end{pmatrix}Y\) .

Let us now prove the theorem.
\(\bullet \)  Assume that \(G_2\)  is formed by diagonal matrices. Then, \(D\)  is diagonal, \(G_d\)  is an algebraic group of diagonal matrices and the reduction is explained in Section REF .
\(\bullet \) 
Assume that \(G_2\)  is reducible but not formed by diagonal matrices. Up to a conjugation, we may assume that \(G_2\)  is formed by upper triangular matrices. By [1]}, the upper triangular entry can be any nonzero element of \(C\) .
We can assume that the matrix \(D\)  is of the form \(\begin{pmatrix}a&0&0 \\0 &b&c \\0&0&d\end{pmatrix}\)  with \(c\ne 0\) . Let us first reduce the diagonal system \([\mathrm {Diag}(a,b,d)]\) . This will change the elements \(a,b,c,d\)  but, simplifying notations, let us denote by \(a,b,c,d\)  the new ones. With Remark REF  and Theorem REF , we are looking for a reduction matrix of the form \(T:=\begin{pmatrix}1&0&0 \\0&1&t \\0&0&1\end{pmatrix}\) .
We denote by \([D^{\prime }]\)  a reduced system, \(D^{\prime } = \begin{pmatrix}a&0&0 \\0 &b&c^{\prime } \\0&0&d\end{pmatrix} \)  for a \(c^{\prime }\in \mathbf {k}\) .
The only non-trivial equality in \(\phi (T)D = D^{\prime }T \)  is on the \((2,3)\)  entry:
\(c+ d \phi (t) = bt +c^{\prime }.\) 
We have \(c^{\prime }\ne 0\) , otherwise the gauge transformation \(T_2 =\begin{pmatrix}1&t \\0&1\end{pmatrix}\) 
would transform \([\phi (T_2)A_2 T_2^{-1}]\)  into a diagonal system, a contradiction. For all \(c^{\prime }\ne 0\) , the algebraic group generated by \( \begin{pmatrix}a&0&0 \\0 &b&c^{\prime } \\0&0&d\end{pmatrix} \)  is the same, so we may take \(t=0\)  and \(c^{\prime }=c\)  and the system is already reduced.
\(\bullet \)  When \(G_2\)  is irreducible and imprimitive, up to a conjugation, it is of the form
\(G_2=G_{2}^{d}\cup G_{2}^{a}\) , where \(G_{2}^{d}\)  is formed by diagonal matrices and \(G_{2}^{a}\)  by anti-diagonal matrices.
We also have a decomposition \(G_{d}=G_{d}^{d}\cup G_{d}^{a}\) , where \(G_{d}^d\subset G_1 \times G_{2}^{d}\)  is formed by diagonal matrices, and \(G_{d}^{a}\subset G_1 \times G_{2}^{a}\)  by matrices of the form \(\begin{pmatrix}\star &0&0 \\0 &0&\star \\0&\star &0\end{pmatrix}\) .
We can assume that the matrix \(D\)  is of the form \(\begin{pmatrix}a&0&0 \\0 &0&b \\0&c&0\end{pmatrix}\)  since otherwise \(G_2\)  would be reducible.
Remark 6.2 Note that \(D_{[2]}\)  is a diagonal matrix. By Lemma REF , the connected components of the difference Galois groups of \([D]\)  and \([D_{[2]}]\)  are the same. So if we are only interested in computing the connected component of \(G\)  we may just reduce the diagonal system \([D_{[2]}]\) , see Section REF  for more details.

Since we know how to compute the Galois group of a diagonal system, we are able to compute a reduction matrix \(P\in \mathrm {GL}_{3}(\mathbf {k})\)  such that the system \(\phi ^2(Y) = \phi ^2(P)D_{[2]}P^{-1}Y \)  is reduced. Consider \(B:=\phi (P)DP^{-1}\) , we have \(B_{[2]}=\phi ^2(P)D_{[2]}P^{-1}\)  thus \([B_{[2]}]\)  is reduced. Let us prove that the system \([B]\)  is already reduced.
Let \(H\)  be the smallest algebraic group such that \(B\in H(\mathbf {k})\) . We have \(G_d\subset H\)  (property of Galois groups, see Theorem REF ).
By Lemma REF , the Galois group of the \(\phi ^2\) -system \([B_{[2]}]\)  and the Galois group of the \(\phi \) -system \([B]\)  have the same connected component. Since \([D_{[2]}]\)  and \([B_{[2]}]\)  have the same Galois group, and \([B_{[2]}]\)  is reduced we find
\(H^0=G_d^0\) . We recall that \(H\)  is the smallest algebraic group such that \(B\in H(\mathbf {k})\) . Then, \(H/H^0=H/G_d^0\)  is generated by a single element, so it is cyclic (and finite since it is an algebraic group, see [16]}).
Since \(G_d/G_d^0\)  is finite cyclic,
\(G_d=G_d^0 \times \mathbb {Z}/m^{\prime }\mathbb {Z}, \quad H=G_d^0 \times \mathbb {Z}/n^{\prime }\mathbb {Z}\) 
for integers \(m^{\prime },n^{\prime }\) .
With Theorem REF  and Lemma REF , there exists \(k\)  such that \(B_{[k]}\in G_d^0 (\mathbf {k})\) .
Since, \(G_d\subset H\) , we have \(m^{\prime }\leqslant n^{\prime }\) . By Theorem REF , there exists \(P_1\in H(\mathbf {k})\)  such that \(B_{red}=\phi (P_1)BP_{1}^{-1}\in G_d (\mathbf {k})\)  is reduced.
Since \(H\)  is an algebraic group defined over \(C\) , the class of \(\phi ^{k}B\)  in \(H/G_d^0\)  is independent of \(k\) . Then, the integer \(m^{\prime }\)  (resp. \(n^{\prime }\) ) is the smallest such that \(B_{red,[m^{\prime }]}\in G_d^0 (\mathbf {k})\)  (resp. \(B_{[n^{\prime }]}\in G_d^0 (\mathbf {k})\) ). Since \(G_d^0\)  is composed by diagonal matrices and \(B,B_{red}\)  are not diagonal (otherwise \(G_2\)  would be reducible), we find that \(m^{\prime }=2m\) , \(n^{\prime }=2n\)  for some integers \(m,n\) .
We have \(B_{red,[2]}=\phi (B_{red})B_{red}=\phi ^2(P_{1})B_{[2]}P_{1}^{-1} \in G_d^0 \times \mathbb {Z}/m\mathbb {Z}(\mathbf {k})\) .
Since \(H_{[2]}:= G_d^0 \times \mathbb {Z}/n\mathbb {Z}\)  is the smallest algebraic group such that \(B_{[2]}\in H_{[2]}(\mathbf {k})\) 
and since \([B_{[2]}]\)  is reduced as a \(\phi ^2\) -system, we have \(n\leqslant m\) , proving that \(m^{\prime }=n^{\prime }\) . Then \(G_d=H\)  and \([B]\)  is already reduced.
\(\bullet \)  When \(G_2\)  is irreducible and primitive, by [12]}, \(G_2= \det (G_2)\times \operatorname{SL}_2(C)\) . We recall that \(\det (G_2)\)  is the difference Galois group of \(\phi (Y)=dY\)  with \(d:=\det \left(\phi (T_2)A_2 T_2^{-1}\right)\) .
Let \(R:=\mathrm {Diag}(r_1,r_2)\)  be a reduction matrix of the bloc diagonal system
\(\phi (Y)=BY\)  where \(B:=\begin{pmatrix}\phi (T_1)\alpha T_1^{-1}&0\\0 &d\end{pmatrix}\) .
Then,
\(\phi (R)BR^{-1} = \mathrm {Diag}(\underbrace{\phi (r_1T_1)\alpha (T_1r_1)^{-1}}_{:=B_1}, \underbrace{\phi (r_2)d r_2^{-1}}_{:=B_2})\, .\) 
Let us prove that \(T:=\mathrm {Diag}(r_1,r_2,1)\)  is a reduction matrix of \([D]\) . Let \( H\)  be the minimal algebraic group such that \(B_{red}:=\phi (T)D T^{-1}\in H(\mathbf {k})\) . We set \(B_{red}=\begin{pmatrix}B_{red,1} & 0 \\ 0 & B_{red,2}\end{pmatrix}\) . By construction, we have \(B_{red,1} = B_1\)  and \(\det (B_{red,2}) = B_2\) .
Note that \(G_d\)  is a subgroup of \(G_1\times \det (G_2) \operatorname{SL}_2(C)\) .
Furthermore, since \(G_2\)  is irreducible and primitive, \(G_d\)  contains \(\lbrace 1\rbrace \times \operatorname{SL}_2(C)\) . Consider the map
\(\begin{array}{rccl}\xi : & G_1 (\mathbf {k}) \times \det (G_2) \operatorname{SL}_2 (\mathbf {k}) & \rightarrow & (\mathbf {k}^{*})^2 \\& (A,B) & \mapsto & (A,\det (B)) \, .\end{array}\) 
Let \( \lbrace 1\rbrace \times \operatorname{SL}_2\subset H_1\subsetneq H_2\subset G_1\times G_2\)  be two algebraic groups. Since the kernel of \(\xi \)  is \( \lbrace 1\rbrace \times \operatorname{SL}_2(\mathbf {k})\) , we have \(\xi (H_1(\mathbf {k}))\subsetneq \xi (H_2(\mathbf {k}))\) . Furthermore, \(\xi \)  is injective on the set of algebraic subgroups of \((G_1\times G_2)(\mathbf {k})\)  containing \( \lbrace 1\rbrace \times \operatorname{SL}_2(\mathbf {k})\) .
By Theorem REF , we find that \(G_d\subset H\)  so that we have \(\xi (G_d(\mathbf {k}))\subset \xi (H(\mathbf {k}))\) . Since \(R:=\mathrm {Diag}(r_1,r_2)\)  is a reduction matrix of the bloc diagonal system
\(\phi (Y)=BY\) , we have
\(\xi (H(\mathbf {k}))\subset \xi (G_d(\mathbf {k}))\) , and then \(\xi (G_d(\mathbf {k}))= \xi (H(\mathbf {k}))\) .
From the above injectivity property, \(G_d(\mathbf {k})=H(\mathbf {k})\) .
Then \(T:=\mathrm {Diag}(r_1,r_2,1)\)  is a reduction matrix of \([D]\) .
So in all cases we should be able to reduce the block diagonal system \([D]\)  and find an associated reduction matrix, denoted by \(T^{\prime }\) .
The next step consists in reducing the system \([A]\) . We will see that finding the reduction matrix is equivalent to finding vector solutions in \(\mathbf {k}\)  of \(\phi \) -linear systems with coefficients in \(\mathbf {k}\)  that we will explicit. We consider
\(B:=\phi (T^{\prime })A T^{\prime -1}.\) 
The matrix \(B\)  is of the form \( \begin{pmatrix}D_1& \widetilde{A} \\0 &D_2\end{pmatrix}\) . By construction, the difference Galois group of \([B]\)  is \(G\) , so let us compute the latter. We write \(B_d:=\begin{pmatrix}D_1&0 \\0 & D_2\end{pmatrix}\) .
Recall that \(G_d\)  is the Galois group of \([B_d]\) , which is a reduced system thanks to the first step.
The Galois group \(G\)  is conjugated to a subgroup of
\(\left\lbrace  \begin{pmatrix}C_1& \begin{matrix} c_1& c_2 \end{matrix} \\0 & C_2\end{pmatrix}\Bigg | \begin{pmatrix}C_1& 0 \\0 & C_2\end{pmatrix} \in G_d, c_1,c_2\in C \right\rbrace  =G_d \rtimes U,\) 
where \(U=\left\lbrace  \begin{pmatrix}1& c_1& c_2 \\0 & 1 &0 \\0&0&1\end{pmatrix}\Bigg | c_1,c_2\in C \right\rbrace \)  is isomorphic to two copies of the additive group.
By Lemma REF , there exists \(T:=\begin{pmatrix}1& X \\0 & I_2\end{pmatrix}\in \mathrm {GL}_3 (\mathbf {k})\) 
such that \([\phi (T)BT^{-1}]\)  is reduced.
Let \(F:=\phi (T)BT^{-1}\) .
We have \(F= \begin{pmatrix}D_1& A^{\prime } \\0 & D_2\end{pmatrix}\)  where \(A^{\prime } = - XD_1 +\widetilde{A}+\phi (X)D_2 \) , that is,
\(\widetilde{A}+\phi (X)D_2=XD_1 +A^{\prime }.\) 
Let \(G^{u}=G \cap U\) . It is an algebraic subgroup of \(U\)  so it is of dimension 0, 1 or 2.
Lemma 6.3 The dimension of the algebraic group \(G^{u}\)  is 0 if and only if there exists \(X\in \mathbf {k}^2\)  such that
\(\widetilde{A}+\phi (X)D_2=XD_1.\) 
In this case \([F]\) , where \(F= B_d\) , is a reduced system equivalent to \([B]\)  with the gauge transformation \(T:=\begin{pmatrix}1& X \\0 & I_2\end{pmatrix}\)  and the Galois group \(G\)  is \(G_d\) .

From Theorem REF , the dimension of \(G^{u}\)  is 0 if and only if \(A^{\prime } = (0\quad 0) \) .
Lemma 6.4 Assume that the dimension of \(G^u\)  is not 0. Then, the dimension of \(G^u\)  is 1 if and only if \(D_2\)  is a triangular matrix (lower or upper triangular, including the diagonal matrices).
If it is the case, we can assume that \(D_2\)  is a lower triangular matrix. Three cases occur:
\(\bullet \)  Case where \(D_2\)  is lower triangular but not diagonal. In this case
\(G = \left\lbrace  \begin{pmatrix}C_1& \begin{matrix} 0&c \end{matrix} \\0 & C_2\end{pmatrix}\Bigg | \begin{pmatrix}C_1& 0 \\0 & C_2\end{pmatrix} \in G_d, c\in C \right\rbrace .\) 
\(\bullet \)  Case where \(D_2\)  is diagonal but not a homotecy. In this case, \(G\)  is the same group as before or \(\left\lbrace  \begin{pmatrix}C_1& \begin{matrix} c&0 \end{matrix} \\0 & C_2\end{pmatrix}\Bigg | \begin{pmatrix}C_1& 0 \\0 & C_2\end{pmatrix} \in G_d, c\in C \right\rbrace \) , depending if there is a solution in \(\mathbf {k}\)  of some linear equations with coefficients in \(\mathbf {k}\)  (see equations (REF ) or (REF )).
\(\bullet \)  Case where \(D_2\)  is a homotecy. In this case,
\(G = \left\lbrace  \begin{pmatrix}C_1& \begin{matrix} \lambda c & \mu c \end{matrix} \\0 & C_2\end{pmatrix}\Bigg | \begin{pmatrix}C_1& 0 \\0 & C_2\end{pmatrix} \in G_d, c\in C \right\rbrace .\) 
where \(\lambda , \mu \in C^2 \setminus \lbrace (0,0)\rbrace \)  can be explicited, see (REF ).
In each case, the proof gives an explicit gauge transformation and a reduced system.

Let \(Y\)  be such that \(h= \begin{pmatrix}1&Y \\0 & I_2\end{pmatrix} \in G^{u}\) .
For \(g=\begin{pmatrix}a_g & C_g \\0 & B_g\end{pmatrix} \in G\) , let us compute \(ghg^{-1}\in G^u\) . We write
\(ghg^{-1}= \begin{pmatrix}1&Z\\0 & I_2\end{pmatrix} \) , so that we have \(\begin{pmatrix}a_g & C_g \\0 & B_g\end{pmatrix}\begin{pmatrix}1& Y \\0 & I_2\end{pmatrix} =\begin{pmatrix}1&Z \\0 & I_2\end{pmatrix} \begin{pmatrix}a_g & C_g \\0 & B_g\end{pmatrix}\) .
Then, \(a_gY + C_g = C_g + ZB_g\)  proving that
\(ghg^{-1}= \begin{pmatrix}1&a_g Y B_g^{-1} \\0 & I_2\end{pmatrix} \in G^u\) .
If the dimension of \(G^{u}\)  is 1 then \(a_g Y B_{g}^{-1}=cY\)  for some \(c\in C^*\) . Taking the transposition, we find \((B_g^{-1})^{t}Y^{t}=c^{\prime }Y^t\)  for some \(c^{\prime }\in C^*\) .
So \(Y^{t}\)  is an eigenvector of any elements \((B_g^{-1})^{t}\) . This means that the elements \(B_g\)  are all conjugated to lower triangular matrices (or upper triangular matrices) and \(Y^{t}\)  is necessarily a common eigenvector. Since \([F]\)  is a reduced system, \(D_2\)  is also a triangular matrix.
When \(D_2\)  is a triangular matrix, up to conjugation, we can assume that \(D_2\)  is lower triangular. In what follows, we denote by \(\widetilde{A}_1\)  and \(\widetilde{A}_2\)  the entries of \(\widetilde{A}\) . We distinguish three cases:
\(\bullet \)  Case where \(D_2\)  is lower triangular but not diagonal. We set \(D_2 = \begin{pmatrix}d_1 & 0 \\ d_3 & d_4\end{pmatrix}\) . In this case the system \([B]\)  is equivalent to the system \([F]\)  where \(F\)  is of the form \(\begin{pmatrix}D_1& \begin{matrix} 0& f \end{matrix} \\0 &D_2\end{pmatrix}\) , for a certain \(f\in C^\star \) , thanks to a gauge transformation \(T:=\begin{pmatrix}1& x_1& x_2 \\0 & 1 &0 \\0&0&1\end{pmatrix}\) . Recall that \(\widetilde{A}+\phi (X)D_2=XD_1+A^{\prime }\) . Since the first entry of \(A^{\prime }\)  has to be 0, we obtain
\( \widetilde{A}_1+\phi (x_1)d_1+\phi (x_2)d_3= x_1 D_1.\) 
We may solve it
with for example \(x_1=1\) , \(x_2 = \phi ^{-1}(x)\)  where \(x= (D_1-\widetilde{A}_1-d_1)d_3^{-1}\in \mathbf {k}\) . In that case the equation on the second entry gives \(f = \widetilde{A}_2 + \phi (x_2)d_4 - D_1 x_2\) .
From Theorem REF , this implies that
\(G\subset \left\lbrace  \begin{pmatrix}C_1& \begin{matrix} 0&c \end{matrix} \\0 & C_2\end{pmatrix}\Bigg | \begin{pmatrix}C_1& 0 \\0 & C_2\end{pmatrix} \in G_d, c\in C \right\rbrace .\) 
Since \(G = G_d \rtimes G^u\) , we obtain that the previous inclusion is an equality.
\(\bullet \)  Case where \(D_2\)  is diagonal but not a homotecy. We set \(D_2 = \mathrm {Diag}(d_1,d_4)\) . Up to a conjugation, we have \(G^{u}=\left\lbrace  \begin{pmatrix}1& c&0 \\0 & 1 &0 \\0&0&1\end{pmatrix}, c\in C \right\rbrace \)  or \(G^{u}=\left\lbrace  \begin{pmatrix}1& 0&c \\0 & 1 &0 \\0&0&1\end{pmatrix}, c\in C \right\rbrace \) .
Using the same notations as before, we obtain that \(G^u\)  is the first one, resp. the second one, if there exists a solution \(y\in \mathbf {k}\)  of the equation
\(\widetilde{A}_2 + \phi (y)d_4 = D_1y \, ,\) 

resp. of the equation
\(\widetilde{A}_1 + \phi (y)d_1 = D_1y \, .\) 

(Only one of these two equations has a solution in \(\mathbf {k}\)  because if it is not the case, the solutions \(x_1, x_2\)  are such that \(X:=(x_1\quad x_2)\in \mathbf {k}^2\)  is a solution of (REF ), a contradiction since the dimension of \(G^u\)  is not 0.)
With the same reasoning as before, we obtain that the Galois group \(G\)  is
\(\left\lbrace  \begin{pmatrix}C_1& \begin{matrix} c & 0 \end{matrix} \\0 & C_2\end{pmatrix}\Bigg | \begin{pmatrix}C_1& 0 \\0 & C_2\end{pmatrix} \in G_d, c\in C \right\rbrace  \text{ or } \left\lbrace  \begin{pmatrix}C_1& \begin{matrix} 0&c \end{matrix} \\0 & C_2\end{pmatrix}\Bigg | \begin{pmatrix}C_1& 0 \\0 & C_2\end{pmatrix} \in G_d, c\in C \right\rbrace \, ,\) 
if \(G^u\)  is respectively the first or the second algebraic group.
\(\bullet \)  Case where \(D_2\)  is a homotecy. We set \(D_2=dI_2\)  with \(d\in C^\star \) . Let \(\lambda ,\mu \in C\)  not all zero such that
\(G^{u}=\left\lbrace  \begin{pmatrix}1& \lambda c& \mu c \\0 & 1 &0 \\0&0&1\end{pmatrix}, c\in C \right\rbrace \) . From Lemma REF , since \(G = G_d \rtimes G^u\) , there exists \(T:=\begin{pmatrix}1 & X \\ 0 & I_2\end{pmatrix}\)  such that \(\phi (T)B=FT\) ,
where \([F]\)  is reduced with \(F=\begin{pmatrix}D_1& \begin{matrix} \lambda f& \mu f\end{matrix} \\0 &D_2\end{pmatrix}\) .
This is equivalent to
\(\widetilde{A}+\phi (X)D_2=D_1X+\begin{pmatrix}\lambda f & \mu f \end{pmatrix}\, ,\) 
that is,
\(\left\lbrace \begin{array}{l}d \phi (x_1) = D_1 x_1 - \widetilde{A}_1 +\lambda f \\d \phi (x_2) = D_1 x_2 - \widetilde{A}_2 +\mu f\end{array}\right.\) 
where \(x_1,x_2\)  are the coordinates of \(X\) .
Taking \(\mu \)  times the first line minus \(\lambda \)  times the second, we find that \(x=\mu x_1-\lambda x_2\)  is solution of \(d\phi (x)=D_1 x- \mu \widetilde{A}_1 +\lambda \widetilde{A}_2\) .
We then find that
this is equivalent to the fact that the vector \(Y:= \begin{pmatrix} \lambda \\ \mu \\ x \end{pmatrix}\)  is solution of
\(\phi (Y)=\begin{pmatrix}1 & 0 & 0 \\0&1&0\\\widetilde{A}_2d^{-1} & -\widetilde{A}_1 d_2^{-1} & D_1d^{-1}\end{pmatrix}Y.\) 
Conversely, any nonzero solution of the latter system in \(\mathbf {k}^3\)  will give a reduction matrix, and a reduced form.
If the dimension of \(G^{u}\)  is 2, \(G=G_d \rtimes U\) . In that situation, the system is already reduced.

Imprimitive case
Assume now that \(G\)  is irreducible and treat the case where \(G\)  is imprimitive. This case is solved in Section REF .
It is imprimitive if and only if the difference Galois group of \(\phi ^3 Y=A_{[3]}Y\)  is diagonal. We use the reducible case (with \(\phi \)  replaced by \(\phi ^3\) ) to check this property. In that case we are able to compute \(d\in \mathbf {k}^*\) , solution of the Riccati equation corresponding to \(\phi ^3 Y=A_{[3]}Y\) . We now follow Proposition REF .
Let us compute a reduced form of \(\phi (y)=dy\) , that is compute \(f\in \mathbf {k}^*\)  such that \(\phi (y)=d\frac{\phi (f)}{f}y\)  is reduced. Then, a reduced form is given by
\(\left( \begin{array}{ccc}0&1&0\\0 &0& f^{-1}\\\phi (f)d & 0&0\end{array}\right) \)  with reduction matrix \(\mathrm {Diag}(1,1,f)\) .

Primitive case
Assume now that \(G\)  is irreducible and primitive. Let \(D(G)\)  be the derived subgroup. By [18]}, either \(D(G)\)  is \(\mathrm {SL}_3(C)\) , either it is isomorphic to \(\mathrm {PSL}_2(C)\) . Since \(\mathrm {SO}_3(C)\)  is also a primitive subgroup of \(\mathrm {SL}_3(C)\) , it is isomorphic to \(\mathrm {PSL}_2(C)\) .
The matrices commuting with the two mentioned groups are homotecies and we find that the center is isomorphic to an algebraic subgroup of \(C^*\) . Then the center of \(G\)  is isomorphic to \(\det (G)^{1/3}=\lbrace  c\in C^*| c^3 \in \det (G)\rbrace  \) , with the writing
\(A\mapsto \det (A)^{1/3}\times A\det (A)^{-1/3}\)  (note that we may take the roots of elements of \(C\)  since the latter is algebraically closed).
So let us write
\(G\sim \det (G)^{1/3} D(G)\) .
The group \(\det (G)\)  may be computed with an equation of order one, \(\phi (y)=\det (A)y\) .
We want to give a criterion to decide whether \(D(G)=\mathrm {SO}_3(C)\)  or not. Let us prove the following lemma.
Lemma 6.5 
Assume that \(G\)  is irreducible and primitive. Let \(\overline{\mathbf {k}}\)  be the algebraic closure of \(\mathbf {k}\) . We may extend \(\phi \)  on the latter. The following facts are equivalent.

\(D(G)=\mathrm {SO}_3(C)\) .

there exist \(T\in \mathrm {GL}_3(\mathbf {k})\) , \(\lambda \in \mathbf {k}^*\)  and \(B\in \mathrm {SO}_3(\mathbf {k})\)  such that
\(\phi (T)AT^{-1}=\lambda B.\) 

there exist \(T\in \mathrm {GL}_3(\overline{\mathbf {k}})\) , \(\lambda \in \overline{\mathbf {k}}^*\)  and \(B\in \mathrm {SO}_3(\overline{\mathbf {k}})\)  such that (REF ) holds.


Recall that \(G\sim \det (G)^{1/3} D(G)\) , where \(D(G)\in \lbrace \mathrm {SO}_3(C),\mathrm {SL}_3(C) \rbrace \) . By Theorem REF , \(D(G)=\mathrm {SO}_3(C)\)  if and only if
there exist \(T\in \mathrm {GL}_3(\mathbf {k})\) , \(\lambda \in \mathbf {k}^*\)  (with \(\lambda ^3\in \det (G)(\mathbf {k})\) ) and \(B\in \mathrm {SO}_3(\mathbf {k})\)  such that (REF ) holds. So the first two items are equivalent. If the second item holds, then the third item holds. Conversely assume that the third item holds.
Consider \(\overline{G}\) , the Galois group over \(\overline{\mathbf {k}}\) . By Theorem REF , \(\overline{G}\sim \det (\overline{G})^{1/3} \mathrm {SO}_3(C)\) .
By Galois correspondence, see [5]}, \(\overline{G}\)  is a subgroup of \(G\)  and \(G/\overline{G}\)  is finite. Since \(G\sim \det (G)^{1/3} D(G)\) , where \(D(G)\in \lbrace \mathrm {SO}_3(C),\mathrm {SL}_3(C) \rbrace \) , this shows that \(D(G)\)  cannot be \(\mathrm {SL}_3(C)\) . Then \(D(G)= \mathrm {SO}_3(C)\) .
The equation (REF ) is non linear and may be complicated to solve. Let us see how we may reduce to a linear equation.
Let us first prove a technical result that will be used in the sequel.
Lemma 6.6 
Let \(K\)  be a field of characteristic zero.
Let \(X\in \mathrm {GL}_n (K)\)  be a symmetric matrix. Then, there exist \(F,D\in \mathrm {GL}_n (K)\)  with \(D\)  diagonal such that \(X=FDF^t\) .

Let \(E_{i,j}\)  be the square matrix of order \(n\)  whose \((i,j)\)  entry is 1 and the other entries are 0.
For \(i\ne j\) , let \(T_{i,j}\)  be the corresponding transvection matrix, that is \(\mathrm {Id}+E_{i,j}\) .
If we consider
\(T_{i,j}X(T_{i,j})^{t}\)  we make the following operations: the column \(C_i\)  of \(X\)  is replaced by \(C_{j}+C_i\)  and then the line \(L_i\)  is replaced by \(L_{i}+L_j\) . Take \(i=1\) . This shows that \(X_{1,1}\)  is replaced by \(X_{1,1}+X_{j,1}+X_{1,j} +X_{j,j}=X_{1,1}+2X_{1,j}+X_{j,j}\) .
Let us see how to reduce to the case \(X_{1,1}\ne 0\) . Assume \(X_{1,1}=0\) . If there exists \(j>1\)  such that \(X_{j,j}\ne 0\)  then we replace \(X\)  by \(PXP^t\)  where \(P = E_{1,j} + E_{j,1} + \sum \limits _{k\ne 1,j}E_{k,k}\)  is the permutation matrix which exchanges the lines 1 and \(j\) . We have \(P= P^{-1} = P^{t}\) . If \(X_{j,j}=0\)  for all \(j\) , we consider \(j\)  such that \(X_{1,j}\ne 0\)  (such \(j\)  exists otherwise the first line is only composed by 0 entries, contradicting the fact that \(X\)  is invertible). Let us perform
\(T_{1,j}X(T_{1,j})^{t}\)  so that \(X_{1,1}\)  is replaced by \(X_{1,1}+2X_{1,j}+X_{j,j}=2X_{1,j}\ne 0\) . So we may reduce to the case where \(X_{1,1}\ne 0\) .
For \(i\in \lbrace 2,\ldots ,n\rbrace \) , let \(T := \mathrm {Id} + \alpha _i E_{i,1}\)  with \(\alpha _i:=- X_{i,1}/X_{1,1}\) . Computing \(TXT^{t}\) , \(X_{i,1}\)  is replaced by \(\alpha _i X_{1,1} + X_{i,1} = 0\)  thus, as in a Gaussian Pivot, we force \(X_{2,1}=\dots =X_{n,1}=0\) . We also have \(X_{1,2}=\dots =X_{1,n}=0\)  since the matrix obtained remains symmetric. We repeat the procedure to the other lines and columns to find the result.
Toward an efficient way to check that (REF ) holds, let us prove the following.
Lemma 6.7 The following facts are equivalent.

There exist \(T\in \mathrm {GL}_3(\overline{\mathbf {k}})\) , \(\lambda \in \overline{\mathbf {k}}^*\)  and \(B\in \mathrm {SO}_3(\overline{\mathbf {k}})\)  such that (REF ) holds.

There exist \(\lambda \in \overline{\mathbf {k}}^* \) , \(X\in \mathrm {GL}_3(\overline{\mathbf {k}})\)  such that \(X=X^t\) , and \(A XA^t =\lambda ^2\phi (X)\) .


Let us prove that the first point implies the second.
Let us assume the existence of \(T\in \mathrm {GL}_3(\overline{\mathbf {k}})\) , \(\lambda \in \mathbf {\overline{\mathbf {k}}}^*\) , and \(B\in \mathrm {SO}_3(\overline{\mathbf {k}})\)  such that (REF ) holds. Let us set \(P:=T^{-1}\)  and note that \(P^t\)  is the inverse of \(T^t\) . Using \(BB^t=\mathrm {Id}\)  we find that (REF ) implies
\(\phi (T)APP^t A^t \phi (T^t)=\lambda ^2 Id.\) 
The latter is equivalent to
\(APP^t A^t =\lambda ^2\phi (PP^t).\) 
We obtain the result if we set \(X=PP^t\) .
Conversely, assume that the second item holds. By Lemma REF , let us write \(X=FDF^t\)  with matrices whose coefficients are in \(\overline{\mathbf {k}}\) . Since \(\overline{\mathbf {k}}\)  is algebraically closed, \(F\sqrt{D}\)  has coefficients in \(\overline{\mathbf {k}}\)  and we may write
\(X=F\sqrt{D}(\sqrt{D})^t F^t\) , where \(\sqrt{D}\)  is any diagonal matrix whose square is \(D\) . Let us perform \(\phi (T)AT^{-1}\)  where \(T\in \mathrm {GL}_3(\overline{\mathbf {k}})\)  is the inverse of \(F\sqrt{D}\) . Note that \(X=T^{-1}(T^{-1})^t \) . It suffices to prove that \(B=\phi (T)AT^{-1}\lambda ^{-1}\in \mathrm {SO}_3(\overline{\mathbf {k}})\) .
Then,
\(B B^t=\lambda ^{-2} \phi (T)AT^{-1}(T^{-1})^t A^{t}\phi (T^t)=\lambda ^{-2} \phi (T)AX A^{t}\phi (T^t).\) 
We now use \(A XA^t =\lambda ^{2}\phi (X)\)  to deduce that the latter equals
\( \phi (T)\phi (X) \phi (T^t). \) 
With \(X=T^{-1}(T^{-1})^t \) , we deduce that \(\phi (T)\phi (X) \phi (T^t)\)  is the identity, that is \(B\in \mathrm {SO}_3(\overline{\mathbf {k}})\) .
If we replace \(X\)  by \(X^{\prime }:=X\det (X)^{-1/3}\in \mathrm {SL}_3 (\overline{\mathbf {k}})\) , we find \(A X^{\prime }A^t =\det (A)^{2}\phi (X^{\prime })\) . Since there are no proper finite difference field extension of \(\phi \) , we find that \(X^{\prime }\in \mathrm {SL}_3(\mathbf {k})\) . With Lemma REF , and Lemma REF , we have proved the following result.
Proposition 6.8 
Assume that \(G\)  is irreducible and primitive. Then, \(D(G)=\mathrm {SO}_3(C)\)  if and only if there exists \(X\in \mathrm {SL}_3(\mathbf {k})\)  such that \(X=X^t\)  and \(A XA^t =\det (A)^{2}\phi (X)\) .

Proposition REF  then reduces the criterion on \(D(G)\)  to look at solutions in \(\mathbf {k}\)  of linear \(\phi \) -difference systems in coefficients in \(\mathbf {k}\)  with 6 unknowns.
Let us now see how to compute the reduced form. First consider the case where \(D(G)= \mathrm {SO}_3(C)\) .
Let \(X\in \mathrm {SL}_3(\mathbf {k})\)  such that \(X=X^t\)  and \(A XA^t =\det (A)^{2}\phi (X)\) . Let us write \(X=FDF^t\)  as in Lemma REF . Note that the proof of Lemma REF  is constructive so \(F\)  and \(D\)  may be effectively computed.
Let us perform the gauge transformation \(\phi (T)AT^{-1}\)  where \(T\in \mathrm {GL}_3(\overline{\mathbf {k}})\)  is the inverse of \(F\sqrt{D}\) . If \(T\)  does not have entries in \(\mathbf {k}\)  we take another solutions \(X\)  until we find a corresponding \(T\in \mathrm {GL}_3(\mathbf {k})\) .
We compute \(\det (G)\)  as the difference Galois group of an order one system \(\phi (y)=a_0\frac{\phi (\det (T))}{\det (T)} y\)  with reduction matrix \(f\in \mathbf {k}^*\) , that is \(\phi (y)=a_0\frac{\phi (f)}{f}\frac{\phi (\det (T))}{\det (T)} y\)  is reduced with Galois group \(\det (G)\) .
Then, we perform, as in [1]}, the gauge transformation \(\mathrm {Diag}(f,1,1)T\)  to obtain a reduced system \([B]\) .
When \(D(G)=\mathrm {SL}_3 (C)\) , the reduction matrix is given by \(\mathrm {Diag}(f,1,1)\) , where \(f\in \mathbf {k}^*\)  is the reduction matrix of \(\phi (y)=a_0 y\) .
Example 6.9 
Consider \(G\)  the difference Galois group of (REF ) over \(\mathbb {C}(z^{1/*})\) . Assume that \(t\ne 0\) . Assume by contradiction that \(D(G)=\mathrm {SO}_3(\mathbb {C})\) .
The eigenvalues of matrices of \(\mathrm {SO}_3(\mathbb {C})\)  are of the form \((1,a^{\pm 1})\) , \(a\in \mathbb {C}^*\) . Then, the eigenvalues of elements of \(G\)  are for the form \((c,ca^{\pm 1})\) , \(c,a\in \mathbb {C}^*\) . By [21]}, combined with the computation of the Newton polygon in Example REF , \(G\)  contains the so-called theta torus, elements of the form \(\mathrm {Diag}(1,1,d)\) , \(d\in \mathbb {C}^*\) . If the triple \(\mathrm {Diag}(1,1,d)\)  is of the form \((c,ca^{\pm 1})\) , then either \(a=1=c=d\) , either \(a=c=-1\)  and \(d=-1\) . Then, \(\mathrm {Diag}(1,1,2)\)  can never be of the form \((c,ca^{\pm 1})\) , showing that \(D(G)\ne \mathrm {SO}_3(\mathbb {C})\) .


Summary
Let
\(L := \phi ^3 + a_2 \phi ^2 +a_1 \phi +a_0\in \mathbf {k}\left< \phi ,\phi ^{-1}\right>\) 
and let \(G\subset \mathrm {GL}_{3}(C)\)  be the Galois group of \(Ly=0\) .
If the Riccati equation attached to \(L\)  or the similar equation attached to \(L^{\vee }\)  has a solution then \(G\)  is reducible. Otherwise, it is irreducible.
When it is the reducible case, \(L\)  or \(L^{\vee }\)  has a right factor of order 1 denoted by \(\phi -\alpha \) . Therefore, up to an isomorphism, the Galois group \(G\)  is the one of the system
\(\phi (Y)= \left(\begin{array}{c|c}\alpha & 1 \hspace*{8.5359pt} 0 \\\hline 0 & A_2\end{array}\right)Y \, . \) 
We already know how to reduce the systems \([\alpha ]\)  and \([A_2]\)  (order 1 and 2) and we denote respectively by \([\beta ]\)  and \([B_2]\)  these reduced systems. We consider the system \([A]\)  which is equivalent to this previous system with \(A\)  of the form
\(\begin{pmatrix}\beta &\star \\0 & B_2\end{pmatrix}\) . To reduce the system \([A]\)  and compute its Galois group, which is \(G\)  up to an isomorphism, we proceed in two steps:
(i)
We reduce the bloc diagonal system \([D]\)  where \(D = \begin{pmatrix}\beta &0 \\0 & B_2\end{pmatrix}\)  and we find an associated reduction matrix denoted by \(T^{\prime }\) .

We reduce the system \([B]\)  where \(B:=\phi (T^{\prime })A T^{\prime -1}\) . Doing this, we introduce some linear equations and we know which is the group \(G\)  if we know that there exists a solution or not of these equations (see equations (REF ), (REF ), (REF ), (REF ))

When it is not the reducible case, we have to distinguish between the imprimitive case and the primitive case. Let \(A:=A_L\) . We know that it is imprimitive if and only if the difference Galois group of \(\phi ^3 Y=A_{[3]}Y\)  is diagonal. We use the reducible case (with \(\phi \)  replaced by \(\phi ^3\) ) to check this property.
Finally, when it is irreducible and primitive, we have to distinguish between \(D(G)=\mathrm {SO}_3 (C)\)  and \(D(G)=\mathrm {SL}_3 (C)\) . We have \(D(G)=\mathrm {SO}_3 (C)\) , if and only if there is a symmetric solution of the linear difference equation \(A XA^t =\det (A)^{2}\phi (X)\) .
Combining the facts proved in Examples REF , REF , REF , and REF , we then find the Galois group of (REF ) over \(\mathbb {C}(z^{1/*})\) :
Theorem 6.10 
For all \(t\ne 0\) , the difference Galois group of (REF ) over \(\mathbb {C}(z^{1/*})\)  is \(\mathrm {GL}_3(\mathbb {C})\) .

Application to the differential transcendence
Let \(\mathbf {k}\)  be a field of characteristic zero and \((\mathbf {k},\phi ,\partial )\)  be a \(\mathcal {C}^1\) -field with no proper finite difference field extension, equipped with an automorphism \(\phi \) , and a derivation \(\partial \) , that is an additive morphism satisfying the Leibnitz rule \(\partial (fg)=\partial (f)g+f\partial (g)\) . Let us assume that \(\phi \)  and \(\partial \)  commute. In our examples, we may take \(\partial =\partial _z\)  (case S and E), and \(\partial =z \partial _z\)  (case Q). In the Mahler case, we could adapt as in [22]} the framework with the derivation \(\partial = z \partial _z \log (z)\)  but this will complicate the exposition of a general criterion, so let us drop the Mahler case in what follows.
Let us consider \(R\) , a ring extension of \(\mathbf {k}\)  such that \(\phi \)  and \(\partial \)  extend on \(R\) . We say that \(f\in R\)  is \(\partial \) -algebraic over \(\mathbf {k}\)  if there exists \(n\in \mathbb {N}\)  and a nonzero \(P\in \mathbf {k}[X_0,\dots , X_n]\)  such that \(P(f,\dots , \partial ^n f)=0\) . We say that \(f\)  is \(\partial \) -transcendent over \(\mathbf {k}\)  otherwise. In our examples, \(f\)  is \(\partial \) -algebraic over \(\mathbf {k}\)  if and only if it is \(\partial _z\) -algebraic over \(\mathbf {k}\) . Many proof of \(\partial \) -transcendence of solutions of \(\phi \) -equation are based on the difference Galois theory. Roughly speaking, this kind of theorem says that if the difference Galois group is sufficiently big, then the nonzero solutions of the linear equation are \(\partial \) -transcendent. Let \(f\in R^*\)  be a solution of
\( a_3\phi ^3 (y)+ a_2 \phi ^2 (y)+a_1 \phi (y)+a_0 y=0, \quad \text{where}\quad a_i\in \mathbf {k}\quad \text{and}\quad a_0 a_3 \ne 0.\) 
Consider the dual
\(\sum _{i=0}^{3} \phi ^{-i} (a_{i})\phi ^{-i}\)  that is equivalent to
\( \phi ^3(a_0)\phi ^3 (y)+ \phi ^2(a_1) \phi ^2 (y)+\phi (a_2) \phi (y)+a_3 y=0, \quad \text{where}\quad a_i\in \mathbf {k}.\) 
Theorem 7.1
Let us assume that

there is no \(u\in \mathbf {k}\)  such that
\(a_3 u\phi (u)\phi ^2 (u)+a_2 u\phi (u)+ a_1 u+a_0=0.\) 

there is no \(u\in \mathbf {k}\)  such that
\(\phi ^3(a_0) u\phi (u)\phi ^2 (u)+\phi ^2(a_1) u\phi (u)+ \phi (a_2) u+a_3=0.\) 

there is no \(g\in \mathbf {k}\)  and nonzero linear differential operator \(L\in C[\partial ]\) , such that
\(L(\partial (a_0/a_3 )/(a_0/a_3))=\phi (g)-g. \) 

Then, \(f\)  is \(\partial \) -transcendent over \(\mathbf {k}\) .

Let \(G\)  be the difference Galois group of the equation of order three satisfied by \(f\) . The first assumption ensures that the operator has no right factor of order one and the second assumption ensures that the operator has no left factor of order one. So the operator is irreducible and then the difference Galois group is irreducible. When \(G\)  is imprimitive, this is the same reasoning as [23]}. When \(G\)  is primitive, it contains \(\mathrm {SO}_3 (C)\)  and we now follow the proof of [23]}.
