Search

The dictionary learning problem concerns the task of representing data as sparse linear sums drawn from a smaller collection of basic building blocks. In application domains where such techniques are deployed, we frequently encounter datasets where some form of symmetry or invariance is present. Motivated by this observation, we develop a framework for learning dictionaries for data under the constraint that the collection of basic building blocks remains invariant under such symmetries. Our procedure for learning such dictionaries relies on representing the symmetry as the action of a matrix group acting on the data, and subsequently introducing a convex penalty function so as to induce sparsity with respect to the collection of matrix group elements. Our framework specializes to the convolutional dictionary learning problem when we consider integer shifts. Using properties of positive semidefinite Hermitian Toeplitz matrices, we develop an extension that learns dictionaries that are invariant under continuous shifts. Our numerical experiments on synthetic data and ECG data show that the incorporation of such symmetries as priors are most valuable when the dataset has few data-points, or when the full range of symmetries is inadequately expressed in the dataset., Comment: 30 pages, 23 figures

As recounted in this paper, the idea of groups is one that has evolved from some very intuitive concepts. We can do binary operations like adding or multiplying two elements and also binary operations like taking the square root of an element (in this case the result is not always in the set). In this paper, we aim to find the operations and actions of Lie groups on manifolds. These actions can be applied to the matrix group and Bi-invariant forms of Lie groups and to generalize the eigenvalues and eigenfunctions of differential operators on Rn. A Lie group is a group as well as differentiable manifold, with the property that the group operations are compatible with the smooth structure on which group manipulations, product and inverse, are distinct. It plays an extremely important role in the theory of fiber bundles and also finds vast applications in physics. It represents the best-developed theory of continuous symmetry of mathematical objects and structures, which makes them indispensable tools for many parts of contemporary mathematics, as well as for modern theoretical physics. Here we did work flat out to represent the mathematical aspects of Lie groups on manifolds.

We determine the minimal degree permutation representations of all finite groups with trivial soluble radical, and describe applications to structural computations in large finite matrix groups that use the output of the CompositionTree algorithm. We also describe how this output can be used to help find an effective base and strong generating set for such groups. We have implemented the resulting algorithms in Magma , and we report on their performance.

Many significant real world challenges arise as optimization problems on different classes of control systems. In particular, ordinary differential equations with symmetries. The purpose of this review article is twofold. First, we give the information we have about the class of Linear Control Systems ΣG on a low dimension matrix Lie group G. Second, we invite the Mathematical community to consider possible applications through the Pontryagin Maximum Principle for ΣG. In addition, we challenge some theoretical open problems. The class ΣG is a perfect generalization of the classical Linear Control System on the Abelian group Rn. Let G be a Lie group of dimension two or three. Related to ΣG, this review describes the actual results about controllability, the time-optimal Hamiltonian equations and, the Pontryagin Maximum Principle. We show how to build ΣG, through several examples on low dimensional matrix groups.

For an isotropic reductive group G satisfying a suitable rank condition over an infinite field k, we show that the sections of the A 1 -fundamental group sheaf of G over an extension field L / k can be identified with the second group homology of G ( L ) . For a split group G, we provide explicit loops representing all elements in the A 1 -fundamental group. Using A 1 -homotopy theory, we deduce a Steinberg relation for these explicit loops.

We describe algorithms and heuristics that allow us to express arbitrary elements of SLn (Z) and Sp2n (Z) as products of generators in particular "standard" generating sets. For elements obtained experimentally as random products, it produces product expressions whose lengths are competitive with the input lengths., Comment: ISSAC 2018

It is shown, that the mapping class group of a surface of the genus g > 1 admits a faithful representation into the matrix group GL (6g-6, Z). The proof is based on a categorical correspondence between the Riemann surfaces and the so-called toric AF-algebras.

We introduce a method for obtaining provable polynomial time solutions of problems in nonabelian algebraic cryptography. This method is widely applicable, easier to apply, and more efficient than earlier methods. After demonstrating its applicability to the major classic nonabelian protocols, we use this method to cryptanalyze the Triple Decomposition key exchange protocol, the only classic group theory based key exchange protocol that could not be cryptanalyzed by earlier methods.

We present a practical cryptanalysis of WalnutDSA, a digital signature algorithm trademarked by SecureRF. WalnutDSA uses techniques from permutation groups, matrix groups and braid groups, and is designed to provide post-quantum security in lightweight IoT device contexts. The attack given in this paper bypasses the E-Multiplication\(^{\text {TM}}\) and cloaked conjugacy search problems at the heart of the algorithm and forges signatures for arbitrary messages in approximately two minutes. We also discuss potential countermeasures to the attack.

We describe an algorithm to compute a composition tree for a matrix group defined over a finite field, and show how to use the associated structure to carry out computations with such groups; these include finding composition and chief series, the soluble radical, and Sylow subgroups.

We define pseudomatrix multiplication on the set of rectangular matrices which is different from the standard matrix multiplication. We give examples of pseudomatrix groups. The usual matrix multiplication is a particular case of pseudomatrix multiplication.

This article considers the work done to find a suitable group implementation for the creation of new cryptosystems which work is based on the use of finite non-commutative algebraic groups. In particular, some subgroup structures of matrix groups over finite fields are described, and one of the possible methods for representing of open texts as elements of the group is used. At the preliminary stage of the cryptosystem, the developed concept of generating keys is described, and recommendations are given for selecting the elements of the secret key. The structure and features of the cryptosystem under investigation are given, earlier studies and experiments that were carried out in this field are considered. To generate subgroups of the groups under study, it is proposed to use elementary transvections, in particular, long and short root unipotent elements. A classification of certain groups of the Chevalley type by types A l -D l is provided. Some assumptions are made concerning the possible improvement of reliability and speed of such cryptosystems based upon the finite non-commutative algebraic groups, as well as relating to the prospects of further research in this direction and minimizing or eliminating the shortcomings of this data encryption model.

Let R be a commutative ring of characteristic zero and G be an arbitrary group. In the present paper we classify the groups G for which the set of symmetric elements with respect to the classical involution of the group ring RG is Lie metabelian.

I give my view of the early history of the discovery of hyperbolic structures on knot complements from my early work on representations of knot groups into matrix groups to my meeting with William Thurston in 1976. (This article was written by Robert Riley about ten years before his death in 2000 and never submitted for publication. An explanation of why it is being published now and some information about Riley and this article is given in the article by Brin, Jones and Singerman which accompanies this article in this issue of the [journal | arxiv].), 14 pages, 1 figure

This paper investigates the critical group of a faithful representation of a finite group. It computes the order of the critical group in terms of the character values, and gives some restrictions on its subgroup structure. It also computes the precise structure of the critical group both for the regular representation of any finite group, and for the reflection representation of the symmetric group., 8 pages

We study soluble matrix groups over commutative rings and transfer some results of the theory of soluble matrix groups over a field to the case of soluble matrix groups over commutative rings.

The sign pattern of a real matrix M is the (0, 1, −1)-matrix obtained from M by replacing each entry by its sign. Let N ∈ ℝ n×n be a group invertible matrix. Let Q(N) be the set of real matrices with the same sign pattern as N. For any , if is group invertible and the group inverses of N and have the same sign pattern, then N is called an S2GI matrix. In this article, we present the existence and the representations for the group inverse of some block matrices with one or two full rank sub-blocks, and give a family of block matrices which are S2GI matrices. Applying these results, we can partially determine the sign pattern of the solution of singular linear system with index one.

Let F be a field, and let \(\mathbb{G}\) be the standard Borel subgroup of the symplectic group Sp(2m, F). In this paper, we characterize the bijective maps ϕ: \(\mathbb{G}\) → \(\mathbb{G}\) satisfying ϕ[x, y] = [ϕ(x), ϕ(y)].

We find a method to recognize the characteristic of a simple group of Lie type G from its Dirichlet polynomial P G ( s ) . This is enough to complete the proof of the following statement: if G is a simple group, H is a finite group and P G ( s ) = P H ( s ) , then H / Frat ( H ) ≅ G .

We find new examples of classical matrix groups that cannot be generated by an involution and an element of order 3. In particular, we show that PSU5(4) and Sp6(q) for odd q are not (2,3)-generated.

We present a new approach to designing public-key cryptosystems based on covers and logarithmic signatures of non-abelian finite groups. Initially, we describe a generic version of the system for a large class of groups. We then propose a class of 2-groups and argue heuristically about the system’s security. The system is scalable, and the proposed underlying group, represented as a matrix group, affords significant space and time efficiency.

The present manuscript aims at illustrating fundamental challenges and solutions arising in the design of learning theories by optimization on manifolds in the context of complex-valued neural systems. The special case of a unitary unimodular group of matrices is dealt with. The unitary unimodular group under analysis is a low dimensional and easy-to-handle matrix group. Notwithstanding, it exhibits a rich geometrical structure and gives rise to interesting speculations about methods to solve optimization problems on manifolds. Also, its low dimension allows us to treat most of the quantities involved in computation in closed form as well as to render them in graphical format. Some numerical experiments are presented and discussed within the paper, which deal with complex-valued independent component analysis.

We present a practical algorithm to construct the subgroup of the general linear group that preserves a system of bilinear or sesquilinear forms on a vector space defined over a finite field. Components include efficient algorithms to construct the Jacobson radical and the group of units of a matrix algebra.

The purpose of this paper is to extend the symmetric representation of the rigid body equations from the group SO (n) to other groups. These groups are matrix subgroups of the general linear group that are defined by a quadratic matrix identity. Their corresponding Lie algebras include several classical semisimple matrix Lie algebras. The approach is to start with an optimal control problem on these groups that generates geodesics for a left-invariant metric. Earlier work by Bloch, Crouch, Marsden, and Ratiu defines the symmetric representation of the rigid body equations, which is obtained by solving the same optimal control problem in the particular case of the Lie group SO (n). This paper generalizes this symmetric representation to a wider class of matrix groups satisfying a certain quadratic matrix identity. We consider the relationship between this symmetric representation of the generalized rigid body equations and the generalized rigid body equations themselves. A discretization of this symmetric representation is constructed making use of the symmetry, which in turn give rise to numerical algorithms to integrate the generalized rigid body equations for the given class of matrix Lie groups.

We describe an algorithm for computing a chief series, the soluble radical, and two other characteristic subgroups of a matrix group over a finite field, which is intended for matrix groups that are too large for the use of base and strong generating set methods. The algorithm has been implemented in Magma by the second author.

We present algorithms for testing nilpotency of matrix groups over finite fields, and for deciding irreducibility and primitivity of nilpotent matrix groups. The algorithms also construct modules and imprimitivity systems for nilpotent groups. In order to justify our algorithms, we prove several structural results for nilpotent linear groups, and computational and theoretical results for abstract nil-potent groups, which are of independent interest.

We describe practical algorithms for computing a polycyclic presentation and for facilitating a membership test for a polycyclic subgroup of GL(d,Q). A variation of this method can be used to check whether a finitely generated subgroup of GL(d,Q) is solvable or solvable-by-finite. We report on our implementations of the algorithms for determining a polycyclic presentation and checking solvability.

We develop a notion of a *-product on a general abelian group, establish a Weyl calculus for operators on the group and connect these with the representation theory of an associated Heisenberg group. This can all be viewed as a generalization of the familiar theory for R. A symplectic group is introduced and a connection with the classical Cayley transform is established. Our main application is to finite groups, where consideration of the symbol calculus for the cyclic groups provides an interesting alternative to the usual matrix form for linear transformations. This leads to a new basis for sl(n) and a decomposition of this Lie algebra into a sum of C*artan subalgebras.

A pair of pants is a building block of oriented surfaces. The purpose of this paper is to formulate the matrix presentations of elements of the Teichmuller space of a pair of pants. In the level of the matrix group , we shall show that an odd number of traces of matrix presentations of the generators of the fundamental group of should be negative.

In this article we give several results and problems on the permutation groups, having an interest for cryptography.

Let G be a Lie group acting on a vector space V. I say that a vector field u:V→V is orbital if for all p in V, u(p) is tangent to the orbit of p at p. Now let the vector space V and the vector space tangent to G at the identity have inner products. In this setting I define a simple map (which I call quasi-projection) which transforms any vector field on V into an orbital one. I use the quasi-projection map to define flows which compute canonical forms.

In this expository article, which is a slightly expanded version of the lecture given at the All Ireland Algebra Days (Belfast, 16–19 May, 2001), we first recall a technique recently developed by F. Dalla Volta and A. Lucchini to study generation properties of finite groups. We then discuss some problems in permutation groups, linear groups and profinite groups where this technique has proved useful. Finally, we comment on some results and problems related to probability

We present an algorithm to decide whether or not a matrix group defined over a finite field is tensor-induced.

Finite groups of matrices appear early as examples in a first course in abstract algebra, and most of the time these examples are given with integral entries. While these groups provide a setting in which to illustrate new concepts and to pose problems, they also have surprising and beautiful properties. For example, Minkowski proved the unexpected result that GL(n, Z), the group of n x n matrices having inverses whose entries are also integers, has only finitely many isomorphism classes of finite subgroups. As a consequence, there are only finitely many possible orders for elements of GL(n, Z); fortunately, the possible orders can be determined using linear algebra. In general, the number of possible orders increases as n increases, but even here we have the surprising result that no new possible orders are obtained when going from GL(2k, Z) to GL(2k + 1, 7). This paper is an exposition of these and other related results and questions. Although finite groups of integral matrices have a long history, most of the beautiful theorems concerning them do not appear in texts and are not known to many algebraists (for example, the first named author). While still an area of active research (see [7], [12], [23], and [24]), major parts are accessible to students; indeed, this paper has its origin in a term paper written by the second author for a beginning modem algebra course that used [9] as a text. One of our goals for this paper is to be a source of problems, readings, and projects for other students; the topic seems ideal since it synthesizes results from number theory, algebra, and linear algebra, gives a natural and somewhat gentle introduction to deeper subjects not yet encountered by a beginning algebra student, has historical features, and could be a subject of continuing student research. With this goal in mind, the authors have included exercises and have tried to organize the paper so that parts can be read independently, or given to students in outline form. Our second goal is to give the reader examples of current research in the area.

By Hamilton operators, generalized quaternions have been expressed in terms of 4×4 matrices. In this paper, geometric applications of these matrices in generalized 4-space Eαβ^4 are given. We also show that the set of these matrices with the group operation of matrix multiplication is Lie group of 6-dimension., Hamilton operatorleri ile bir gelişmiş kuaterniyon 4×4 matrisleri ile gösterilmiştir. Bu makalede matrislerin uygulamaları gelişmiş uzay’da verilmiştir. Ayrıca, bu matrislerin kümesi matris çarpım ile altı boyutlu bir Lie grubu oluşturulmuştur

This chapter is intended to give a summary of Lie groups and Lie algebras for computer graphics, including an example from interpolations and blending of motions and deformation. In animation and filmmaking procedure, we want to get a smooth transition of the drawing of given starting and ending point (the drawings at these points are called key frame). This problem can be understood as an interpolation, so that various approach have been proposed and used in Computer Graphics. After the seminal work so-called ARAP (as-rigid-as-possible), serious properties of matrix groups have been taken into account both in theoretical and in computational point of view. To understand and develop these properties, we here employ a Lie theoretic approach.

The braid group B n B_n can be defined as the mapping class group of the n n -punctured disk. A group is said to be linear if it admits a faithful representation into a group of matrices over R \mathbf R . Recently Daan Krammer has shown that a certain representation of the braid groups is faithful for the case n = 4 n=4 . In this paper, we show that it is faithful for all n n .

In this note, we explicitly describe the automorphism group of the R-algebra of strictly upper triangular n×n matrices over an arbitrary commutative ring.

In this paper we consider numerical methods for solving nonlinear equations on matrix Lie groups. Recently Owren and Welfert (Technical Report Numerics, No 3/1996, Norwegian University of Science and Technology, Trondheim, Norway, 1996) have proposed a method where the original nonlinear equation F(Y)=0 is transformed into a nonlinear equation on the Lie algebra of the group, thus Newton-type methods may be applied which require the evaluation of exponentials of matrices. Here the previous transformation will be performed by the Cayley approximant of the exponential map. This approach has the advantage that no exponentials of matrices are needed. The numerical tests reported in the last section seem to show that our approach is less expensive and provides a larger convergence region than the method of Owren and Welfert.

In this paper we describe a suite of new algorithms for studying polycyclic matrix groups—algorithms for testing membership and for uncovering the polycyclic structure of the group. We also describe an algorithm for deciding whether or not a group is solvable, which, in the important context of subgroups ofGL (n,Z), is equivalent to deciding whether or not a group is polycyclic. Algorithms were developed in Baumslag et al. (1991. The algorithmic theory of polycyclic-by-finite groups. J. Algebra, 142, 118–149) for all of these problems, but the algorithms in this paper represent a first step toward finding practical algorithms: experiments show that they are fast enough to be useful in studying some reasonably complex examples using current technology.

We study a connectionvia group representation theory, between the problem of describing the invariant factors of a product of two matrices over a principal ideal domain and the problem of describing the spectrum of a sum of two Hermitian matrices.

We discuss pattern problems for matrix groups and solve one of such problems for a class of nilpotent groups.

We introduce a new matrix theory to investigate finite group actions on spaces. Given a finite group action, we associate it with a family of orbit matrices. The spectral radius of an action is also introduced. It is shown that the spectral raduis is bounded below by a constant depending only on some geometric invariants of the underlying Riemannian manifolds. The relation between the eigenspaces of orbit matrices and regular representations of finite groups are also investigated. In particular, we obtain that the eigenvalues of orbit matrices reveal some structures of the groups. 1. Introduction. In this note we shall discuss the relation between pairwise distances of orbit points of finite groups acting effectively and isometrically on compact Riemannian manifolds and their group structures. Our approach is to consider corresponding matrices of these pairwise distances and then relate the eigenspaces of these matrices to the regular representation of the groups. The motivation of these ideas traces back to the papers (Cl, 2), (R), (W2, 3). To get a sense of how the pairwise distances of the orbit points can reveal the structure of the group itself, let us consider the following two simple examples.