Algorithmic Minimization of Non-zero Entries in 0,1-Matrices

In this paper we present algorithms which work on pairs of 0,1- matrices which multiply again a matrix of zero and one entries. When applied over a pair, the algorithms change the number of non-zero entries present in the matrices, meanwhile their product remains unchanged. We establish the conditions under which the number of 1s decreases. We recursively define as well pairs of matrices which product is a specific matrix and such that by applying on them these algorithms, we minimize the total number of non-zero entries present in both matrices. These matrices may be interpreted as solutions for a well known information retrieval problem, and in this case the number of 1 entries represent the complexity of the retrieve and information update operations.

Matricial Model for the Study of Lower Bounds

Let V be an array. The range query problem concerns the design of data structures for implementing the following operations. The operation update(j,x) has the effect vj ← vj + x, and the query operation retrieve(i,j) returns the partial sum vi + ... + vj. These tasks are to be performed on-line. We define an algebraic model – based on the use of matrices – for the study of the problem. In this paper we establish as well a lower bound for the sum of the average complexity of both kinds of operations, and demonstrate that this lower bound is near optimal – in terms of asymptotic complexity.

Hausdorff Approximation of Functions Different from Zero at One Point - Implementation in Programming Environment Mathematica

ACM Computing Classification System (1998): G.1.2.

A Characterization of Varieties of Associative Algebras of Exponent two

∗The first author was partially supported by MURST of Italy; the second author was par- tially supported by RFFI grant 99-01-00233.

Fermat's Equation in Matrices

The Fermat equation is solved in integral two by two matrices of determinant one as well as in finite order integral three by three matrices.

Differential Balanced Trees and (0,1) Matrices

* The research was supported by INTAS 00-397 and 00-626 Projects.