Linear operators preserving invariants of nonbinary boolean matrices

There is an isomorphism between the matrices over the Boolean algebra of subsets of a k-element set and the k-tuples of Boolean binary (i.e. zero-one) matrices. This isomorphism allows many problems concerning nonbinary Boolean matrices to the referred to the binary ease. However, there are some features of the general (i.e. nonbinary) case that have not been mentioned, although they differ somewhat from the binary case. We exhibit characterizations of the linear operators that preserve several invariants of matrices over finite Boolean algebras to illustrate the differences and similarities of the general vs. the binary cases. We employ a canonical form that is useful in applying the isomorphism.     

On linear operators strongly preserving invariants of Boolean matrices

Let U _k be the general Boolean algebra and T a linear operator on M _m,n (U _k ). If for any A in M _m,n (U _k ) (M _n (U _k ), respectively), A is regular (invertible, respectively) if and only if T(A) is regular (invertible, respectively), then T is said to strongly preserve regular (invertible, respectively) matrices. In this paper, we will give complete characterizations of the linear operators that strongly preserve regular (invertible, respectively) matrices over U _k . Meanwhile, noting that a general Boolean algebra U _k is isomorphic to a finite direct product of binary Boolean algebras, we also give some characterizations of linear operators that strongly preserve regular (invertible, respectively) matrices over 169-7 _k from another point of view.     

Term rank preservers of Boolean matrices

We obtain some characterizations of linear operators that preserve the term rank of Boolean matrices. That is, a linear operator over Boolean matrices preserves the term rank if and only if it preserves the term ranks 1 and k(≠1) if and only if it preserves the term ranks 2 and l(≠2). Other characterizations of term rank preservers are given.     

Boolean autoencoders and hypercube clustering complexity

We introduce and study the properties of Boolean autoencoder circuits. In particular, we show that the Boolean autoencoder circuit problem is equivalent to a clustering problem on the hypercube. We show that clustering m binary vectors on the n-dimensional hypercube into k clusters is NP-hard, as soon as the number of clusters scales like ${m^\epsilon (\epsilon >0 )}$ , and thus the general Boolean autoencoder problem is also NP-hard. We prove that the linear Boolean autoencoder circuit problem is also NP-hard, and so are several related problems such as: subspace identification over finite fields, linear regression over finite fields, even/odd set intersections, and parity circuits. The emerging picture is that autoencoder optimization is NP-hard in the general case, with a few notable exceptions including the linear cases over infinite fields or the Boolean case with fixed size hidden layer. However learning can be tackled by approximate algorithms, including alternate optimization, suggesting a new class of learning algorithms for deep networks, including deep networks of threshold gates or artificial neurons.     

On Flat Semimodules over Semirings

The following analog of the characterization of flat modules has been obtained for the variety of semimodules over a semiring R: A semimodule _RA is flat (i.e., the tensor product functor – A preserves all finite limits) iff A is L-flat (i.e., A is a filtered colimit of finitely generated free semimodules). We also give new (homological) characterizations of Boolean algebras and complete Boolean algebras within the classes of distributive lattices and Boolean algebras, respectively, which solve two problems left open in [14]. It is also shown that, in contrast with the case of modules over rings, in general for semimodules over semirings the notions of flatness and mono-.atness (i.e., the tensor product functor – A preserves monomorphisms) are different.     

Vectorial Resilient PC（l） of Order k Boolean Functions from AG-Codes

Propagation criteria and resiliency of vectorial Boolean functions are important for cryptographic purpose (see [1–4, 7, 8, 10, 11, 16]). Kurosawa, Stoh [8] and Carlet [1] gave a construction of Boolean functions satisfying PC(l) of order k from binary linear or nonlinear codes. In this paper, the algebraic-geometric codes over GF(2m) are used to modify the Carlet and Kurosawa-Satoh’s construction for giving vectorial resilient Boolean functions satisfying PC(l) of order k criterion. This new construction is compared with previously known results.     

Homotopy invariance of coherent Witt groups

 We prove the following general homotopy invariance theorem for coherent Witt groups: Let be a flat morphism of separated Gorenstein schemes of finite Krull dimension with affine fibers,i.e. π⁻¹(y) is an affine space over the residue field k(y) for all yY, then the induced homomorphism of coherent Witt groups is an isomorphism. As an application we calculate the (classical) Witt group of the affine hyperbolic sphere over a regular local ring. Received: 22 August 2001; in final form: 22 June 2002 / Published online: 1 April 2003     

Isomorphism Classes of Algebras with Radical Cube Zero II

We study to classify, up to isomorphism, algebras Λ over a field k such that the radical cubed is zero and Λ modulo the radical is a product of copies of k. The number of local quasi-Frobenius k-algebras with the condition is shown to be not less than the cardinality of k. In particular, the canonical forms of those algebras of dimension 5 are presented and their isomorphism classes are completely determined under some conditions on k.      

Commutative Algebras with Radical Cube Zero

Abstract

We present “canonical forms” of finite dimensional (quasi-Frobenius) commutative algebras Λ over a field k such that the radical cubed is zero and Λ modulo the radical is a product of copies of k. We also determine the isomorphism classes of the algebras Λ over some typical fields.     

Maximal commutative subalgebras of matrix algebras

Maximal commutative subalgebras of the algebra of n by n matrices over a field k very rarely have dimension smaller than n. There is a (B, N)-construction which yields subalgebras of this kind. The Courter's algebra that is of this kind was shown a (B, N)-construction where B is the Schur algebra of size 4 and N = k ⁴. That is, the Courter's algebra is isomorphic to B ? (k ⁴)², the idealization of (k ⁴)². It was questioned how many isomorphism classes can be produced by varying the finitely generated faithful B-module N. In this paper, we will show that the set of all algebras B ? N ² fall into a single isomorphism class, where B is the Schur algebra of size 4 and N a finitely generated faithful B-module.     

Théorie tannakienne non commutative

Inspired by a recent paper by Deligne [2], we extend the Tannaka-Krein duility results (over a field) to the non-commutative situation. To be precise, we establish a 1-1 corresponde:ice between ‘tensorial autonomous categories’ equipped with a ‘fibre functor’ (i. e. tannakian categories without the commutativity condition on the tensor product), and ‘quantum groupoids’ (as defined by Maltsiniotis, [9]) which are ‘transitive’ (7.1.). When the base field is perfect, a quantum groupoid over Spec B is transitive iff it is projective and faithfully fiat over B? _k B. Moreover, the fibre functor is unique up to ‘quantum isomorphism’ (7.6.). Actually, we show Tannaka-Krein duality results in the more general setting where there is no monoidal structure on the category (and the functor); the algebraic object corresponding to such a category is a ‘semi-transitive’ coalgebroid (5.2. and 5.8.).     

Idempotent matrix lattices over distributive lattices

In this paper, the partially ordered set of idempotent matrices over distributive lattices with the partial order induced by a set of lattice matrices is studied. It is proved that this set is a lattice; the formulas for meet and join calculation are obtained. In the lattice of idempotent matrices over a finite distributive lattice, all atoms and coatoms are described. We prove that the lattice of quasi-orders over an n-element set Qord(n) is not graduated for n ≥ 3 and calculate the greatest and least lengths of maximal chains in this lattice. We also prove that the interval ([I, J]_≤, ≤) of idempotent (n × n)-matrices over {ie879-01}-lattices is isomorphic to the lattice of quasi-orders Qord(n). Using this isomorphism, we calculate the lattice height of idempotent {ie879-02}-matrices. We obtain a structural criterion of idempotent matrices over distributive lattices. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 4, pp. 121–144, 2007.     

Presentations of the Schützenberger Product of n Groups

ABSTRACT

In this article, we first consider n × n upper-triangular matrices with entries in a given semiring k. Matrices of this form with invertible diagonal entries form a monoid B _n (k). We show that B _n (k) splits as a semidirect product of the monoid of unitriangular matrices U _n (k) by the group of diagonal matrices. When the semiring is a field, B _n (k) is actually a group and we recover a well-known result from the theory of groups and Lie algebras. Pursuing the analogy with the group case, we show that U _n (k) is the ordered set product of n(n ? 1)/2 commutative monoids (the root subgroups in the group case). Finally, we give two different presentations of the Schützenberger product of n groups G ₁,…, G _n , given a monoid presentation ?A _i  | R _i ? of each group G _i . We also obtain as a special case presentations for the monoid of all n × n unitriangular Boolean matrices.     

The Gross conjecture over rational function fields

We study the Gross conjecture for the cyclotomic function field extension k(∧f)/k where k = Fq(t) is the rational function field and f is a monic polynomial in Fq[t]. We prove the conjecture in the Fermat curve case(i.e., when f = t(t - 1)) by a direct calculation. We also prove the case when f is irreducible, which is analogous to the Weil reciprocity law. In the general case, we manage to show the weak version of the Gross conjecture here.     

A Note on the Double Affine Hecke Algebra of Type GL2

We express the double affine Hecke algebra ? associated to the general linear group GL₂(k) (here, k is a field with char(k) ≠ 2) as an amalgamated free product of quadratic extensions over the three-dimensional quantum torus 𝒪_q((k^×)³). With an eye towards proving ring-theoretic results pertaining to ?, a general treatment of amalgamated products of Ore and quadratic extensions is given. We prove an analogue of the Hilbert Basis Theorem for an amalgamated product Q of quadratic extensions and determine conditions for when the one-sided ideals of Q are principal or doubly-generated. Furthermore, we determine sufficient conditions which imply Q is a principal ideal ring. Finally, we construct an explicit isomorphism from ? to the amalgamated free product ring of quadratic extensions over 𝒪_q((k^×)³), a ring known to be noetherian. Therefore, it follows that ? is noetherian.     

Relations between threshold and <Emphasis Type="Italic">k</Emphasis>-interval Boolean functions

Every k-interval Boolean function f can be represented by at most k intervals of integers such that vector x is a truepoint of f if and only if the integer represented by x belongs to one of these k (disjoint) intervals. Since the correspondence of Boolean vectors and integers depends on the order of bits an interval representation is also specified with respect to an order of variables of the represented function. Interval representation can be useful as an efficient representation for special classes of Boolean functions which can be represented by a small number of intervals. In this paper we study inclusion relations between the classes of threshold and k-interval Boolean functions. We show that positive 2-interval functions constitute a (proper) subclass of positive threshold functions and that such inclusion does not hold for any k>2. We also prove that threshold functions do not constitute a subclass of k-interval functions, for any k.     

The k‐ary Montgomery modular inverse over nonbinary computers

This paper presents a k‐ary Montgomery modular inverse algorithm over nonbinary computers by using Sedjelmaci's right shift k‐ary greatest common divisor scheme. Over traditional binary computers, Kaliski's scheme can output Montgomery modular inverse Q ^{? 1}2ⁿ mod P, where P is coprime to Q and n is the bit length of P. Over k‐ary computers, our algorithm can discover the k‐ary Montgomery inverse Q ^{? 1}k^m mod P, where P, Q, and k are pairwise relatively prime positive integers and m = log _kP. In the worst case, the computational cost of our algorithm is O(m²)k‐ary digit operations. Copyright © 2013 John Wiley & Sons, Ltd.     

On the number of curves of genus 2 over a finite field

In this paper we compute the number of curves of genus 2 defined over a finite field k of odd characteristic up to isomorphisms defined over k; the even characteristic case is treated in an ongoing work (G. Cardona, E. Nart, J. Pujolàs, Curves of genus 2 over field of even characteristic, 2003, submitted for publication). To this end, we first give a parametrization of all points in , the moduli variety that classifies genus 2 curves up to isomorphism, defined over an arbitrary perfect field (of zero or odd characteristic) and corresponding to curves with non-trivial reduced group of automorphisms; we also give an explicit representative defined over that field for each of these points. Then, we use cohomological methods to compute the number of k-isomorphism classes for each point in .     

The completeness of the isomorphism relation for countable Boolean algebras

We show that the isomorphism relation for countable Boolean algebras is Borel complete, i.e., the isomorphism relation for arbitrary countable structures is Borel reducible to that for countable Boolean algebras. This implies that Ketonen's classification of countable Boolean algebras is optimal in the sense that the kind of objects used for the complete invariants cannot be improved in an essential way. We also give a stronger form of the Vaught conjecture for Boolean algebras which states that, for any complete first-order theory of Boolean algebras that has more than one countable model up to isomorphism, the class of countable models for the theory is Borel complete. The results are applied to settle many other classification problems related to countable Boolean algebras and separable Boolean spaces. In particular, we will show that the following equivalence relations are Borel complete: the translation equivalence between closed subsets of the Cantor space, the isomorphism relation between ideals of the countable atomless Boolean algebra, the conjugacy equivalence of the autohomeomorphisms of the Cantor space, etc. Another corollary of our results is the Borel completeness of the commutative AF -algebras, which in turn gives rise to similar results for Bratteli diagrams and dimension groups.

     

Generating effective symmetry-breaking predicates for search problems

Consider the problem of testing for existence of an n-node graph G satisfying some condition P, expressed as a Boolean constraint among the n×n Boolean entries of the adjacency matrix M. This problem reduces to satisfiability of P(M). If P is preserved by isomorphism, P(M) is satisfiable iff P(M)∧SB(M) is satisfiable, where SB(M) is a symmetry-breaking predicate—a predicate satisfied by at least one matrix M in each isomorphism class. P(M)∧SB(M) is more constrained than P(M), so it is solved faster by backtracking than P(M)—especially if SB(M) rules out most matrices in each isomorphism class. This method, proposed by Crawford et al., applies not just to graphs but to testing existence of a combinatorial object satisfying any property that respects isomorphism, as long as the property can be compactly specified as a Boolean constraint on the object's binary representation.We present methods for generating symmetry-breaking predicates for several classes of combinatorial objects: acyclic digraphs, permutations, functions, and arbitrary-arity relations (direct products). We define a uniform optimality measure for symmetry-breaking predicates, and evaluate our constraints according to this measure. Results indicate that these constraints are either optimal or near-optimal for their respective classes of objects.