Hermite Normal Form
   HOME





Hermite Normal Form
In linear algebra, the Hermite normal form is an analogue of reduced echelon form for matrices over the integers \Z. Just as reduced echelon form can be used to solve problems about the solution to the linear system Ax=b where x \in \mathbb^n, the Hermite normal form can solve problems about the solution to the linear system Ax=b where this time x is restricted to have integer coordinates only. Other applications of the Hermite normal form include integer programming, cryptography, and abstract algebra. Definition Various authors may prefer to talk about Hermite normal form in either row-style or column-style. They are essentially the same up to transposition. Row-style Hermite normal form A matrix A \in \mathbb^ has a (row) Hermite normal form H if there is a square unimodular matrix U where H=UA. H has the following restrictions: # H is upper triangular (that is, h_=0 for i>j), and any rows of zeros are located below any other row. # The leading coefficient (the first nonzero e ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Linear Algebra
Linear algebra is the branch of mathematics concerning linear equations such as :a_1x_1+\cdots +a_nx_n=b, linear maps such as :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrix (mathematics), matrices. Linear algebra is central to almost all areas of mathematics. For instance, linear algebra is fundamental in modern presentations of geometry, including for defining basic objects such as line (geometry), lines, plane (geometry), planes and rotation (mathematics), rotations. Also, functional analysis, a branch of mathematical analysis, may be viewed as the application of linear algebra to Space of functions, function spaces. Linear algebra is also used in most sciences and fields of engineering because it allows mathematical model, modeling many natural phenomena, and computing efficiently with such models. For nonlinear systems, which cannot be modeled with linear algebra, it is often used for dealing with first-order a ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Lattice (group)
In geometry and group theory, a lattice in the real coordinate space \mathbb^n is an infinite set of points in this space with the properties that coordinate-wise addition or subtraction of two points in the lattice produces another lattice point, that the lattice points are all separated by some minimum distance, and that every point in the space is within some maximum distance of a lattice point. Closure under addition and subtraction means that a lattice must be a subgroup of the additive group of the points in the space, and the requirements of minimum and maximum distance can be summarized by saying that a lattice is a Delone set. More abstractly, a lattice can be described as a free abelian group of dimension n which spans the vector space \mathbb^n. For any basis of \mathbb^n, the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice, and every lattice can be formed from a basis in this way. A lattice may be viewed as a re ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Diophantine Equation
''Diophantine'' means pertaining to the ancient Greek mathematician Diophantus. A number of concepts bear this name: *Diophantine approximation In number theory, the study of Diophantine approximation deals with the approximation of real numbers by rational numbers. It is named after Diophantus of Alexandria. The first problem was to know how well a real number can be approximated ... * Diophantine equation * Diophantine quintuple * Diophantine set {{disambig ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Howell Normal Form
In linear algebra and ring theory, the Howell normal form is a generalization of the row echelon form of a matrix over \Z_N, the ring of integers modulo N. The row spans of two matrices agree if, and only if, their Howell normal forms agree. The Howell normal form generalizes the Hermite normal form, which is defined for matrices over \Z. Definition A matrix A \in \Z_N^ over \Z_N is called to be in ''row echelon form'' if it has the following properties: * Let r be the number of non-zero rows of A. Then the topmost r rows of the matrix are non-zero, * For 1 \leq i \leq r, let j_i be the index of the leftmost non-zero element in the row i. Then j_1 < j_2 < \dots < j_r. With elementary transforms, each matrix in the row echelon form can be reduced in a way that the following properties will hold: * For each 1 \leq i \leq r, the leading element A_ is ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Smith Normal Form
In mathematics, the Smith normal form (sometimes abbreviated SNF) is a normal form that can be defined for any matrix (not necessarily square) with entries in a principal ideal domain (PID). The Smith normal form of a matrix is diagonal, and can be obtained from the original matrix by multiplying on the left and right by invertible square matrices. In particular, the integers are a PID, so one can always calculate the Smith normal form of an integer matrix. The Smith normal form is very useful for working with finitely generated modules over a PID, and in particular for deducing the structure of a quotient of a free module. It is named after the Irish mathematician Henry John Stephen Smith. Definition Let A be a nonzero m \times n matrix over a principal ideal domain R. There exist invertible m \times m and n \times n-matrices S,T (with entries in R) such that the product SAT is \begin \alpha_1 & 0 & 0 & \cdots & 0 & \cdots & 0 \\ 0 & \alpha_2 & 0 & & & & \\ 0 & 0 & \ddots ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Hermite Ring
Charles Hermite () FRS FRSE MIAS (24 December 1822 – 14 January 1901) was a French mathematician who did research concerning number theory, quadratic forms, invariant theory, orthogonal polynomials, elliptic functions, and algebra. Hermite polynomials, Hermite interpolation, Hermite normal form, Hermitian operators, and cubic Hermite splines are named in his honor. One of his students was Henri Poincaré. He was the first to prove that '' e'', the base of natural logarithms, is a transcendental number. His methods were used later by Ferdinand von Lindemann to prove that is transcendental. Life Hermite was born in Dieuze, Moselle, on 24 December 1822, with a deformity in his right foot that would impair his gait throughout his life. He was the sixth of seven children of Ferdinand Hermite and his wife, Madeleine née Lallemand. Ferdinand worked in the drapery business of Madeleine's family while also pursuing a career as an artist. The drapery business relocated to Nancy ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Control Theory
Control theory is a field of control engineering and applied mathematics that deals with the control system, control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive the system to a desired state, while minimizing any ''delay'', ''overshoot'', or ''steady-state error'' and ensuring a level of control Stability theory, stability; often with the aim to achieve a degree of Optimal control, optimality. To do this, a controller with the requisite corrective behavior is required. This controller monitors the controlled process variable (PV), and compares it with the reference or Setpoint (control system), set point (SP). The difference between actual and desired value of the process variable, called the ''error'' signal, or SP-PV error, is applied as feedback to generate a control action to bring the controlled process variable to the same value as the set point. Other aspects ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Principal Ideal Domain
In mathematics, a principal ideal domain, or PID, is an integral domain (that is, a non-zero commutative ring without nonzero zero divisors) in which every ideal is principal (that is, is formed by the multiples of a single element). Some authors such as Bourbaki refer to PIDs as principal rings. Principal ideal domains are mathematical objects that behave like the integers, with respect to divisibility: any element of a PID has a unique factorization into prime elements (so an analogue of the fundamental theorem of arithmetic holds); any two elements of a PID have a greatest common divisor (although it may not be possible to find it using the Euclidean algorithm). If and are elements of a PID without common divisors, then every element of the PID can be written in the form , etc. Principal ideal domains are Noetherian, they are integrally closed, they are unique factorization domains and Dedekind domains. All Euclidean domains and all fields are principal ideal domain ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Dedekind Domain
In mathematics, a Dedekind domain or Dedekind ring, named after Richard Dedekind, is an integral domain in which every nonzero proper ideal factors into a product of prime ideals. It can be shown that such a factorization is then necessarily unique up to the order of the factors. There are at least three other characterizations of Dedekind domains that are sometimes taken as the definition: see below. A field is a commutative ring in which there are no nontrivial proper ideals, so that any field is a Dedekind domain, however in a rather vacuous way. Some authors add the requirement that a Dedekind domain not be a field. Many more authors state theorems for Dedekind domains with the implicit proviso that they may require trivial modifications for the case of fields. An immediate consequence of the definition is that every principal ideal domain (PID) is a Dedekind domain. In fact a Dedekind domain is a unique factorization domain (UFD) if and only if it is a PID. The ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

SageMath
SageMath (previously Sage or SAGE, "System for Algebra and Geometry Experimentation") is a computer algebra system (CAS) with features covering many aspects of mathematics, including algebra, combinatorics, graph theory, group theory, differentiable manifolds, numerical analysis, number theory, calculus, and statistics. The first version of SageMath was released on 24 February 2005 as free and open-source software under the terms of the GNU General Public License version 2, with the initial goals of creating an "open source alternative to Magma, Maple, Mathematica, and MATLAB". The originator and leader of the SageMath project, William Stein, was a mathematician at the University of Washington. SageMath uses a syntax resembling Python's, supporting procedural, functional, and object-oriented constructs. Development Stein realized when designing Sage that there were many open-source mathematics software packages already written in different languages, namely C, C++, ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


PARI/GP
PARI/GP is a computer algebra system with the main aim of facilitating number theory computations. Versions 2.1.0 and higher are distributed under the GNU General Public License. It runs on most common operating systems. System overview The PARI/GP system is a package that is capable of doing formal computations on recursive types at high speed; it is primarily aimed at number theorists. Its three main strengths are its speed, the possibility of directly using data types that are familiar to mathematicians, and its extensive algebraic number theory module. The PARI/GP system consists of the following standard components: * PARI is a C library, allowing for fast computations, and which can be called from a high-level language application (for instance, written in C, C++, Pascal, Fortran, Perl, or Python). * gp is an easy-to-use interactive command line interface giving access to the PARI functions. It functions as a sophisticated programmable calculator which contains mos ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Number Theory Library
NTL is a C++ library for doing number theory. NTL supports arbitrary length integer and arbitrary precision floating point arithmetic, finite fields, vectors, matrices, polynomials, lattice basis reduction and basic linear algebra. NTL is free software released under the GNU Lesser General Public License The GNU Lesser General Public License (LGPL) is a free-software license published by the Free Software Foundation (FSF). The license allows developers and companies to use and integrate a software component released under the LGPL into their own ... v2.1.{{Cite web, title=NTL: A Library for doing Number Theory, url=https://shoup.net/ntl/, access-date=2020-06-06, website=shoup.net References External links Official NTL website C++ libraries Free mathematics software 2015 software ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]