On the optimal evaluation of a set of bilinear forms

Although general theories are beginning to emerge in the area of automata based complexity theory, there are very few general methods or even general problem formulations in the area of arithmetic complexity. In this paper we propose and defined a general model for studying bilinear multiplication in order to provide a common framework for discussing a wide class of problems. The problem of minimizing the number of multiplications required to perform a calculation leads to a problem in matrix algebra relating to the expansion of a given set of matrices as linear combinations of rank-one matrices. In this paper we make a systematic attack on this problem and derived some general results which unify and extend numerous known results.     

On symmetric algorithms for bilinear forms over finite fields

In this paper we study the computation of symmetric systems of bilinear forms over finite fields via symmetric bilinear algorithms. We show that, in general, the symmetric complexity of a system is upper bounded by a constant multiple of the bilinear complexity; we characterize symmetric algorithms in terms of the cosets of a specific cyclic code, and we show that the problem of finding an optimal symmetric algorithm is equivalent to the maximum-likelihood decoding problem for this code.     

An identity for symmetric bilinear forms

We prove an identity for symmetric bilinear forms, and give a simple geometric interpretation.     

Algebraic complexity of the computation of a pair of bilinear forms

The problem mentioned in the titled reduces to the estimation of the rank of a collection of matrices. The rank of a collection of matrices A₁,...,A_e, denoted rk(A₁,...,A_e), is the least number of such one-dimensional matrices that their linear combinations will represent each matrix of the given collection. For an operator A on ⁿ there exists a space V and a diagonal operator B such that; we denote the minimal dimension of such spaces V by d(V)Theorem. For any matrix A we have the equality rk (E,A.)=n+d(A), where E is the identity matrix.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 47, pp. 159–163, 1974.     

A construction for integral symmetric bilinear forms

In this paper we describe a construction, associating with a pair of integral symmetric bilinear forms with identical discriminant forms, an integral symmetric unimodular bilinear form.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 83, pp. 63–66, 1979.     

Invariant symmetric bilinear forms for reflection groups

In this paper we describe a connection between Vinberg's criterion for the existence of an invariant symmetric bilinear form for a geometric representation of a Coxeter groups and other criteria which are formulated in terms of conjugation invariant sets of reflections generating a given group. Similar methods lead to the result that every non-symmetrizable Kac--Moody Lie algebra contains a non-symmetrizable subalgebra of rank 3. Finally we explain how the results for symmetric bilinear forms can also be obtained for skew-symmetric forms. Received 3 March 2000.     

Optimum computation of p bilinear forms

We wish to answer the following question: p matrices B_i, of the same dimension, being given, what is the minimum number of multiplications we have to perform to obtain the p values X^tB_iY, for arbitrary vectors X and Y? We will give first a precise definition of the class of algorithms we consider to evaluate these p bilinear forms, and of our optimization criteria. Then we will characterize an optimal algorithm of this class, and relate the minimum number of multiplications used to the tensorial rank of the p matrices B_i. Properties of this number are given. Finally, the paper will conclude with a proof of the optimality of Strassen's algorithm to perform the product of two 2×2 matrices.     

A note on fan's identity for symmetric bilinear forms

The identity recently discovered by Ky Fan is shown to be a combination of shorter identities expressing determinants that vanish.     

Metric dimension of symplectic dual polar graphs and symmetric bilinear forms graphs

In this paper, by constructing resolving sets of symplectic dual polar graphs and symmetric bilinear forms graphs, we obtain upper bounds on their metric dimension.     

On a question of Sarkozy and Sos for bilinear forms

We prove that, if 2 k₁ k₂, then there is no infinite sequence of positive integers such that the representation functionr(n) = #{(a, a'): n = k₁a + k₂a', a, a' } is constant for nlarge enough. This result completes the previous work of Diracand Moser for the special case k₁ = 1 and answers a questionposed by Sárkozy and Sós.     

On bilinear forms in normal variables

Bilinear forms in normal variables when the matrices of the forms are rectangular are considered. Explicit expressions for the cumulants, joint cumulants and joint cumulants of bilinear and quadratic forms are given. Necessary and sufficient conditions are established for the independence of two bilinear forms as well as a bilinear and a quadratic form. Special cases are shown to agree with known results.     

On the maximal multiplicative complexity of a family of bilinear forms

The number of nonscalar multiplications required to evaluate a general family of bilinear forms is investigated. An upper bound is obtained which is about half that obtained from naive arguments. In certain cases the best possible upper bound is obtained.     

Vector bundles and symmetric bilinear forms over curves of genus one and arbitrary index

Vector bundles over curves of genus one and arbitrary index are investigated and classified, extending Atiayhs results on curves of genus one over algebraically closed fields.These results are used to study the symmetric bilinear forms over such curves, over perfect fields of characteristic not two. Mathematics Subject Classification (2000):Primary 14F05; Secondary 14H60, 14G720, 11E81, 14F05     

On systems of bilinear forms whose minimal division-free algorithms are all bilinear

In this paper we prove that for a certain class of systems of bilinear forms, all minimal division-free algorithms are essentially bilinear. This class includes systems for computing products in finite algebraic extension fields, and systems for computing the products of Toeplitz and Hankel matrices with vectors. Our results, together with the classification theorems of 10., 12., 169–180) completely describe all minimal division-free algorithms for computing these systems. We also prove, as an immediate consequence of our results, that the multiplicative complexity of the quaternion product over a real field is 8.     

On a strange invariant bilinear form on the space of automorphic forms

Let F be a global field and \(G:=SL(2)\). We study the bilinear form \({{\mathcal {B}}}\) on the space of K-finite smooth compactly supported functions on \(G({\mathbb {A}})/G(F)\) defined by

$$\begin{aligned} {{\mathcal {B}}}(f_1,f_2):={{\mathcal {B}}}_{\mathrm {naive}}(f_1,f_2)-\langle M^{-1}{{\mathrm{{CT}}}}(f_1)\, ,{{\mathrm{{CT}}}}(f_2)\rangle , \end{aligned}$$

where \({{\mathcal {B}}}_{\mathrm {naive}}\) is the usual scalar product, \({{\mathrm{{CT}}}}\) is the constant term operator, and M is the standard intertwiner. This form is natural from the viewpoint of the geometric Langlands program. To justify this claim, we provide a dictionary between the classical and ‘geometric’ theory of automorphic forms. We also show that the form \({{\mathcal {B}}}\) is related to S. Schieder’s Picard–Lefschetz oscillators.