Some matrix equations over a finite field

Summary Explicit formulas are found for the number of solutions over a finite field of several matrix equations, for example:X′A+A′X=B. Conditons for solvability are also given. The research for thispaper was supported by National Science Foundation Research Grant G-2990.     

The trace graph of the matrix ring over a finite commutative ring

Let R be a commutative ring and let \({n >1}\) be an integer. We introduce a simple graph, denoted by \({\Gamma_t(M_n(R))}\), which we call the trace graph of the matrix ring \({M_n(R)}\), such that its vertex set is \({M_n(R)^{\ast}}\) and such that two distinct vertices A and B are joined by an edge if and only if \({{\rm Tr} (AB)=0}\) where \({ {\rm Tr} (AB)}\) denotes the trace of the matrix AB. We prove that \({\Gamma_t(M_n(R))}\) is connected with \({{\rm diam}(\Gamma_{t}(M_{n}(R)))=2}\) and \({{\rm gr} (\Gamma_t(M_n(R)))=3}\). We investigate also the interplay between the ring-theoretic properties of R and the graph-theoretic properties of \({\Gamma_t(M_n(R))}\). Hence, we use the notion of the irregularity index of a graph to characterize rings with exactly one nontrivial ideal.     

SomeL-functions of a polynomial ring over a finite field

An L-function involved in the enumeration of certain families of irreducible polynomials over a finite field is studied. For a number of cases, we confirm the hypothesis on zeros of that function, which is an analog of the hypothesis of Riemann and Weyl postulated for algebraic varieties over finite fields. Translated fromAlgebra i Logika, Vol. 35, No. 4, pp. 476–495, July–August, 1996.     

On diameter of the commuting graph of a full matrix algebra over a finite field

It is shown that the commuting graph of a matrix algebra over a finite field has diameter at most five if the size of the matrices is not a prime nor a square of a prime. It is further shown that the commuting graph of even-sized matrices over finite field has diameter exactly four. This partially proves a conjecture stated by Akbari, Mohammadian, Radjavi, and Raja [Linear Algebra Appl. 418 (2006) 161–176].     

A note on polynomial matrix functions over a finite field

Let F_n denote the ring of n×n matrices over the finite field F=GF(q) and let A(x)=A_Nx^N+ ?+ A₁x+A₀?F_n[x]. A function $\text{?:F}{}_{\mathrm{n}}\text{→F}{}_{\mathrm{n}}$ is called a right polynomial function iff there exists an A(x)?F_n[x] such that $\text{?(B)=A}{}_{\mathrm{N}}\text{B}{}^{\mathrm{N}}\text{+?+A}{}_1\text{B+ A}{}_0$ for every B?F_n. This paper obtains unique representations for and determines the number of right polynomial functions.     

On repeated-root multivariable codes over a finite chain ring

In this work we consider repeated-root multivariable codes over a finite chain ring. We show conditions for these codes to be principally generated. We consider a suitable set of generators of the code and compute its minimum distance. As an application we study the relevant example of the generalized Kerdock code in its r-dimensional cyclic version.      

On extended fundamental classes over a finite field

A partition over a finite field is defined which is an extension of the partition defined previously to minimize the number of the fundamental sets required to carry out the additions over the field. Solutions of some trinomial polynomial equations over finite field will be discussed.     

Computing the endomorphism ring of an ordinary elliptic curve over a finite field

We present two algorithms to compute the endomorphism ring of an ordinary elliptic curve E defined over a finite field Fq. Under suitable heuristic assumptions, both have subexponential complexity. We bound the complexity of the first algorithm in terms of , while our bound for the second algorithm depends primarily on log|DE|, where DE is the discriminant of the order isomorphic to End(E). As a byproduct, our method yields a short certificate that may be used to verify that the endomorphism ring is as claimed.     

On the probability that the determinant of an n x n matrix over a finite field vanishes

An expression is derived for the probability that the determinant of an n x n matrix over a finite field vanishes; from this it is deduced that for a fixed field this probability tends to 1 as n tends to ∞.     

Linear sets in the projective line over the endomorphism ring of a finite field

Let \({{\mathrm{{PG}}}}(1,E)\) be the projective line over the endomorphism ring \( E={{\mathrm{End}}}_q({\mathbb F}_{q^t})\) of the \({\mathbb F}_q\)-vector space \({\mathbb F}_{q^t}\). As is well known, there is a bijection \(\varPsi :{{\mathrm{{PG}}}}(1,E)\rightarrow {\mathcal G}_{2t,t,q}\) with the Grassmannian of the \((t-1)\)-subspaces in \({{\mathrm{{PG}}}}(2t-1,q)\). In this paper along with any \({\mathbb F}_q\)-linear set L of rank t in \({{\mathrm{{PG}}}}(1,q^t)\), determined by a \((t-1)\)-dimensional subspace \(T^\varPsi \) of \({{\mathrm{{PG}}}}(2t-1,q)\), a subset \(L_T\) of \({{\mathrm{{PG}}}}(1,E)\) is investigated. Some properties of linear sets are expressed in terms of the projective line over the ring E. In particular, the attention is focused on the relationship between \(L_T\) and the set \(L'_T\), corresponding via \(\varPsi \) to a collection of pairwise skew \((t-1)\)-dimensional subspaces, with \(T\in L'_T\), each of which determine L. This leads among other things to a characterization of the linear sets of pseudoregulus type. It is proved that a scattered linear set L related to \(T\in {{\mathrm{{PG}}}}(1,E)\) is of pseudoregulus type if and only if there exists a projectivity \(\varphi \) of \({{\mathrm{{PG}}}}(1,E)\) such that \(L_T^\varphi =L'_T\).     

On the complexity of matrix reduction over finite fields

In this paper we study the complexity of matrix elimination over finite fields in terms of row operations, or equivalently in terms of the distance in the Cayley graph of generated by the elementary matrices. We present an algorithm called striped matrix elimination which is asymptotically faster than traditional Gauss–Jordan elimination. The new algorithm achieves a complexity of row operations, and operations in total, thanks to being able to eliminate many matrix positions with a single row operation. We also bound the average and worst-case complexity for the problem, proving that our algorithm is close to being optimal, and show related concentration results for random matrices. Next we present the results of a large computational study of the complexities for small matrices and fields. Here we determine the exact distribution of the complexity for matrices from , with n and q small. Finally we consider an extension from finite fields to finite semifields of the matrix reduction problem. We give a conjecture on the behaviour of a natural analogue of GL_n for semifields and prove this for a certain class of semifields.