The maximum order of adjacency matrices of graphs with a given rank

We look for the maximum order m(r) of the adjacency matrix A of a graph G with a fixed rank r, provided A has no repeated rows or all-zero row. Akbari, Cameron and Khosrovshahi conjecture that m(r)?=?2^(r+2)/2 ? 2 if r is even, and m(r)?=?5 · 2^(r?3)/2 ? 2 if r is odd. We prove the conjecture and characterize G in the case that G contains an induced subgraph ${\frac{r}{2}K_2}$ or ${\frac{r-3}{2}K_2+K_3}$ .     

A linear-algebra problem from algebraic coding theory

Given an m×n matrix M over E=GF(q^t) and an ordered basis A={z₁,…,z_t} for field E over K=GF(q), expand each entry of M into a t×1 vector of coordinates of this entry relative to A to obtain an mt×n matrix M¹ with entries from the field K. Let r=rank(M) and r¹=rank(M¹). We show that r?r¹?min{rt,n}, and we determine the number b(m,n,r,r¹,q,t) of m×n matrices M of rank r over GF(q^t) with associated mt×n matrix M¹ of rank r¹ over GF (q).     

On distribution by rank of bases for vector spaces of matrices over a finite field

Let F^m×n_q denote the vector space of all m×n matrices over the finite field F_q of order q, and let $\text{B}\text{=(A}{}_1\text{,A}{}_2\text{,…,A}{}_{\mathrm{mn}}\text{)}$ denote an ordered basis for F^m×n_q. If the rank of A_i is r_i,i=1,2,…,mn, then $\text{B}$ is said to have rank (r₁,r₂,…,r_mn), and the number of ordered bases of F^mxn_q with rank (r₁,r₂,…,r_mn is denoted by N_q(r₁, r₂,…,r_mn). This paper determines formulas for the numbers N_q(r₁,r₂,…,r_mn) for the case m=n=2, q arbitrary, and while some of the techniques of the paper extend to arbitrary m and n, the general formulas for the numbers N_q(r₁,r₂,…,r_mn) seem quite complicated and remain unknown. An idea on a possible computer attack which may be feasible for low values of m and n is also discussed.     

On generalized Hadamard matrices of minimum rank

Generalized Hadamard matrices of order qⁿ⁻¹ (q—a prime power, n2) over GF(q) are related to symmetric nets in affine 2-(qⁿ,qⁿ⁻¹,(qⁿ⁻¹−1)/(q−1)) designs invariant under an elementary abelian group of order q acting semi-regularly on points and blocks. The rank of any such matrix over GF(q) is greater than or equal to n−1. It is proved that a matrix of minimum q-rank is unique up to a monomial equivalence, and the related symmetric net is a classical net in the n-dimensional affine geometry AG(n,q).     

Subspaces of matrices with special rank properties

Let K be a field and let M_m×n(K) denote the space of m×n matrices over K. We investigate properties of a subspace M of M_m×n(K) of dimension n(m-r+1) in which each non-zero element of M has rank at least r and enumerate the number of elements of a given rank in M when K is finite. We also provide an upper bound for the dimension of a constant rank r subspace of M_m×n(K) when K is finite and give non-trivial examples to show that our bound is optimal in some cases. We include a similar a bound for the maximum dimension of a constant rank subspace of skew-symmetric matrices over a finite field.     

On the plane term rank of three dimensional matrices

It is shown that if A is a p>×q×r matrix such that each of the horizontal plane sections of A has full term rank, then the plane term rank of A is greater than m?√m where m= min {p,q,r}. In particular, if A is a three dimensional line stochastic matrix of order n, then the plane term rank of A is greater than n?√n.     

On the rank spread of graphs

For a simple graph G?=?(𝒱, ?) with vertex-set 𝒱?=?{1,?…?,?n}, let 𝒮(G) be the set of all real symmetric n-by-n matrices whose graph is G. We present terminology linking established as well as new results related to the minimum rank problem, with spectral properties in graph theory. The minimum rank mr(G) of G is the smallest possible rank over all matrices in 𝒮(G). The rank spread r _v (G) of G at a vertex v, defined as mr(G)???mr(G???v), can take values ??∈?{0,?1,?2}. In general, distinct vertices in a graph may assume any of the three values. For ??=?0 or 1, there exist graphs with uniform r _v (G) (equal to the same integer at each vertex v). We show that only for ??=?0, will a single matrix A in 𝒮(G) determine when a graph has uniform rank spread. Moreover, a graph G, with vertices of rank spread zero or one only, is a λ-core graph for a λ-optimal matrix A in 𝒮(G). We also develop sufficient conditions for a vertex of rank spread zero or two and a necessary condition for a vertex of rank spread two.     

Recurrent Methods for Constructing Irreducible Polynomials over GF(2s)

The paper is devoted to some results concerning the constructive theory of the synthesis of irreducible polynomials over Galois fields GF(q), q=2^s. New methods for the construction of irreducible polynomials of higher degree over GF(q) from a given one are worked out. The complexity of calculations does not exceed O(n³) single operations, where n denotes the degree of the given irreducible polynomial. Furthermore, a recurrent method for constructing irreducible (including self-reciprocal) polynomials over finite fields of even characteristic is proposed.     

The nonnegative rank factorizations of nonnegative matrices

Let A ∈ P^{m × n}_r, the set of all m × n nonnegative matrices having the same rank r. For matrices A in P^{m × n}_n, we introduce the concepts of “A has only trivial nonnegative rank factorizations” and “A can have nontrivial nonnegative rank factorizations.” Correspondingly, the set P^{m × n}_n is divided into two disjoint subsets P₍₁₎ and P₍₂₎ such that P₍₁₎∪P₍₂₎ = P^{m × n}_n. It happens that the concept of “A has only trivial nonnegative rank factorizations” is a generalization of “A is prime in P^{n × n}_n.” We characterize the sets P₍₁₎ and P₍₂₎. Some of our results generalize some theorems in the paper of Daniel J. Richman and Hans Schneider [9].     

Matching Realization of Uq（sln＋1） of Higher Rank in the Quantum Weyl Algebra Wq（2n）

In the paper, we further realize the higher rank quantized universal enveloping algebra Uq（sln＋1） as certain quantum differential operators in the quantum Weyl algebra Wq （2n） defined over the quantum divided power algebra Sq（n） of rank n. We give the quantum differential operators realization for both the simple root vectors and the non-simple root vectors of Uq（sln＋1）. The nice behavior of the quantum root vectors formulas under the action of the Lusztig symmetries once again indicates that our realization model is naturally matched.     

Reed-Muller codes and Barnes-Wall lattices: Generalized multilevel constructions and representation over GF(2<Superscript><Emphasis Type="Italic">q</Emphasis></Superscript>)

Generalized multilevel constructions for binary RM(r,m) codes using projections onto GF(2 ^q ) are presented. These constructions exploit component codes over GF(2), GF(4),..., GF(2 ^q ) that are based on shorter Reed-Muller codes and set partitioning using partition chains of length-2 ^l codes. Using these constructions we derive multilevel constructions for the Barnes-Wall Λ(r,m) family of lattices which also use component codes over GF(2), GF(4),..., GF(2 ^q ) and set partitioning based on partition chains of length-2 ^l lattices. These constructions of Reed-Muller codes and Barnes-Wall lattices are readily applicable for their efficient decoding.      

On the classification of semifield flocks

A classical lemma of Weil is used to characterise quadratic polynomials f with coefficients GF(qⁿ), q odd, with the property that f(x) is a non-zero square for all x∈GF(q). This characterisation is used to prove the main theorem which states that there are no subplanes of order q contained in the set of internal points of a conic in PG(2,qⁿ) for q?4n²−8n+2. As a corollary to this theorem it then follows that the only semifield flocks of the quadratic cone of PG(3,qⁿ) for those q exceeding this bound are the linear flocks and the Kantor-Knuth semifield flocks.     

Hankel planes

Starting from an (m+1)×(n+1) matrix A one can construct (m+p+1)×(n+1)(p+1) block Toeplitz matrices , p≥0, based on the rows of A. The connections between the ranks of the two matrices is studied by comparing the corresponding vector spaces of row relations R and R(p). A main tool are the Hankel matrices with rows in R. The dimension of R(p) is determined in terms of geometric invariants attached to the Hankel matrices with rows in R. The study of Hankel r-planes of P^m, for r≥1, turns out to be very useful and interesting in itself since they constitute a subvariety of the Grassmannian G(r,m).     

Higher rank numerical ranges and low rank perturbations of quantum channels

For a positive integer k, the rank-k numerical range Λk(A) of an operator A acting on a Hilbert space H of dimension at least k is the set of scalars λ such that PAP=λP for some rank k orthogonal projection P. In this paper, a close connection between low rank perturbation of an operator A and Λk(A) is established. In particular, for 1?r<k it is shown that Λk(A)⊆Λk−r(A+F) for any operator F with rank(F)?r. In quantum computing, this result implies that a quantum channel with a k-dimensional error correcting code under a perturbation of rank at most r will still have a (k−r)-dimensional error correcting code. Moreover, it is shown that if A is normal or if the dimension of A is finite, then Λk(A) can be obtained as the intersection of Λk−r(A+F) for a collection of rank r operators F. Examples are given to show that the result fails if A is a general operator. The closure and the interior of the convex set Λk(A) are completely determined. Analogous results are obtained for Λ_∞(A) defined as the set of scalars λ such that PAP=λP for an infinite rank orthogonal projection P. It is shown that Λ_∞(A) is the intersection of all Λk(A) for k=1,2,…. If A−μI is not compact for all μ∈C, then the closure and the interior of Λ_∞(A) coincide with those of the essential numerical range of A. The situation for the special case when A−μI is compact for some μ∈C is also studied.     

A remark on full rank perfect codes

Any full rank perfect 1-error correcting binary code of length n=2^k-1 and with a kernel of dimension n-log(n+1)-m, where m is sufficiently large, may be used to construct a full rank perfect 1-error correcting binary code of length 2^m-1 and with a kernel of dimension n-log(n+1)-k. Especially we may construct full rank perfect 1-error correcting binary codes of length n=2^m-1 and with a kernel of dimension n-log(n+1)-4 for m=6,7,…,10.This result extends known results on the possibilities for the size of a kernel of a full rank perfect code.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Enumeration of arrays of a given size

Enumeration of arrays whose row and column sums are specified have been studied by a number of people. It has been determined that the function that enumerates square arrays of dimension n, whose rows and columns sum to a fixed non-negative integer r, is a polynomial in r of degree (n ? 1)².In this paper we consider rectangular arrays whose rows sum to a fixed non-negative integer r and whose columns sum to a fixed non-negative integer s, determined by ns = mr. in particular, we show that the functions which enumerate 2 × n and 3 × n arrays with fixed row sums $\text{nr}\text{(2, n)}$ and $\text{nr}\text{(3, n)}$, where the symbol (a, b) denotes the greatest common divisor of a and b, and fixed column sums, are polynomials in r of degrees (n ? 1) and 2(n ? 1) respectively. We have found simple formulas to evaluate these polynomials for negative values, - r, and we show that for certain small negative integers our polynomials will always be zero. We also considered the generating functions of these polynomials and show that they are rational functions of degrees less than zero, whose denominators are of the forms (1 ? y)ⁿ and (1 ? y)²ⁿ?1 respectively and whose numerators are polynomials in y whose coefficients satisfy certain properties. In the last section we list the actual polynomials and generating functions in the 2 × n and 3 × n cases for small specific values of n.     

On extremal matrices of second largest exponent by Boolean rank

Let b = b(A) be the Boolean rank of an n × n primitive Boolean matrix A and exp(A) be the exponent of A. Then exp(A) ? (b − 1)² + 2, and the matrices for which equality occurs have been determined in [D.A. Gregory, S.J. Kirkland, N.J. Pullman, A bound on the exponent of a primitive matrix using Boolean rank, Linear Algebra Appl. 217 (1995) 101-116]. In this paper, we show that for each 3 ? b ? n − 1, there are n × n primitive Boolean matrices A with b(A) = b such that exp(A) = (b − 1)² + 1, and we explicitly describe all such matrices.