|
Combinatorial Matrix Theory
Combinatorial matrix theory is a branch of linear algebra and combinatorics that studies matrices in terms of the patterns of nonzeros and of positive and negative values in their coefficients. Concepts and topics studied within combinatorial matrix theory include: *(0,1)-matrix, a matrix whose coefficients are all 0 or 1 *Permutation matrix, a (0,1)-matrix with exactly one nonzero in each row and each column *The Gale–Ryser theorem, on the existence of (0,1)-matrices with given row and column sums *Hadamard matrix, a square matrix of 1 and –1 coefficients with each pair of rows having matching coefficients in exactly half of their columns *Alternating sign matrix, a matrix of 0, 1, and –1 coefficients with the nonzeros in each row or column alternating between 1 and –1 and summing to 1 * Sparse matrix, a matrix with few nonzero elements, and sparse matrices of special form such as diagonal matrices and band matrices * Sylvester's law of inertia, on the invariance of the nu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 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 lines, planes and rotations. Also, functional analysis, a branch of mathematical analysis, may be viewed as the application of linear algebra to spaces of functions. Linear algebra is also used in most sciences and fields of engineering, because it allows 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 approximations, using the fact that the differential of a multivariate function at a point is the line ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science. Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry, as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving an ''ad hoc'' solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Matrix (mathematics)
In mathematics, a matrix (plural matrices) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a property of such an object. For example, \begin1 & 9 & -13 \\20 & 5 & -6 \end is a matrix with two rows and three columns. This is often referred to as a "two by three matrix", a "-matrix", or a matrix of dimension . Without further specifications, matrices represent linear maps, and allow explicit computations in linear algebra. Therefore, the study of matrices is a large part of linear algebra, and most properties and operations of abstract linear algebra can be expressed in terms of matrices. For example, matrix multiplication represents composition of linear maps. Not all matrices are related to linear algebra. This is, in particular, the case in graph theory, of incidence matrices, and adjacency matrices. ''This article focuses on matrices related to linear algebra, an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Logical Matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets. Matrix representation of a relation If ''R'' is a binary relation between the finite indexed sets ''X'' and ''Y'' (so ), then ''R'' can be represented by the logical matrix ''M'' whose row and column indices index the elements of ''X'' and ''Y'', respectively, such that the entries of ''M'' are defined by :M_ = \begin 1 & (x_i, y_j) \in R, \\ 0 & (x_i, y_j) \not\in R. \end In order to designate the row and column numbers of the matrix, the sets ''X'' and ''Y'' are indexed with positive integers: ''i'' ranges from 1 to the cardinality (size) of ''X'', and ''j'' ranges from 1 to the cardinality of ''Y''. See the entry on indexed sets for more detail. Example The binary relation ''R'' on the set is defined so that ''aRb'' holds if and only if ''a' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Permutation Matrix
In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, when used to multiply another matrix, say , results in permuting the rows (when pre-multiplying, to form ) or columns (when post-multiplying, to form ) of the matrix . Definition Given a permutation of ''m'' elements, :\pi : \lbrace 1, \ldots, m \rbrace \to \lbrace 1, \ldots, m \rbrace represented in two-line form by :\begin 1 & 2 & \cdots & m \\ \pi(1) & \pi(2) & \cdots & \pi(m) \end, there are two natural ways to associate the permutation with a permutation matrix; namely, starting with the ''m'' × ''m'' identity matrix, , either permute the columns or permute the rows, according to . Both methods of defining permutation matrices appear in the literature and the properties expressed in one representation can be easily converted to t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gale–Ryser Theorem
The Gale–Ryser theorem is a result in graph theory and combinatorial matrix theory, two branches of combinatorics. It provides one of two known approaches to solving the bipartite realization problem, i.e. it gives a necessary and sufficient condition for two finite sequences of natural numbers to be the degree sequence of a labeled simple bipartite graph; a sequence obeying these conditions is called "bigraphic". It is an analog of the Erdős–Gallai theorem for simple graphs. The theorem was published independently in 1957 by H. J. Ryser and David Gale. Statement A pair of sequences of nonnegative integers (a_1,\ldots,a_n) and (b_1,\ldots,b_n) with a_1\geq\cdots\geq a_n is bigraphic if and only if \sum_^a_i=\sum_^b_i and the following inequality holds for all k \in \: : \sum^k_ a_i\leq \sum^n_ \min(b_i,k). Sometimes this theorem is stated with the additional constraint b_1\geq\cdots\geq b_n. This condition is not necessary, because the labels of vertices of one partite set ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hadamard Matrix
In mathematics, a Hadamard matrix, named after the French mathematician Jacques Hadamard, is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. In geometric terms, this means that each pair of rows in a Hadamard matrix represents two perpendicular vectors, while in combinatorial terms, it means that each pair of rows has matching entries in exactly half of their columns and mismatched entries in the remaining columns. It is a consequence of this definition that the corresponding properties hold for columns as well as rows. The ''n''-dimensional parallelotope spanned by the rows of an ''n''×''n'' Hadamard matrix has the maximum possible ''n''-dimensional volume among parallelotopes spanned by vectors whose entries are bounded in absolute value by 1. Equivalently, a Hadamard matrix has maximal determinant among matrices with entries of absolute value less than or equal to 1 and so is an extremal solution of Hadamard's maximal determ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Alternating Sign Matrix
In mathematics, an alternating sign matrix is a square matrix of 0s, 1s, and −1s such that the sum of each row and column is 1 and the nonzero entries in each row and column alternate in sign. These matrices generalize permutation matrices and arise naturally when using Dodgson condensation to compute a determinant. They are also closely related to the six-vertex model with domain wall boundary conditions from statistical mechanics. They were first defined by William Mills, David Robbins, and Howard Rumsey in the former context. Examples A permutation matrix is an alternating sign matrix, and an alternating sign matrix is a permutation matrix if and only if no entry equals . An example of an alternating sign matrix that is not a permutation matrix is : \begin 0&0&1&0\\ 1&0&0&0\\ 0&1&-1&1\\ 0&0&1&0 \end. Alternating sign matrix theorem The ''alternating sign matrix theorem'' states that the number of n\times n alternating sign matrices is : \prod_^\frac = \frac. The f ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sparse Matrix
In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse but a common criterion is that the number of non-zero elements is roughly equal to the number of rows or columns. By contrast, if most of the elements are non-zero, the matrix is considered dense. The number of zero-valued elements divided by the total number of elements (e.g., ''m'' × ''n'' for an ''m'' × ''n'' matrix) is sometimes referred to as the sparsity of the matrix. Conceptually, sparsity corresponds to systems with few pairwise interactions. For example, consider a line of balls connected by springs from one to the next: this is a sparse system as only adjacent balls are coupled. By contrast, if the same line of balls were to have springs connecting each ball to all other balls, the system would correspond to a dense matrix. The ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Diagonal Matrix
In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero; the term usually refers to square matrices. Elements of the main diagonal can either be zero or nonzero. An example of a 2×2 diagonal matrix is \left begin 3 & 0 \\ 0 & 2 \end\right/math>, while an example of a 3×3 diagonal matrix is \left begin 6 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end\right/math>. An identity matrix of any size, or any multiple of it (a scalar matrix), is a diagonal matrix. A diagonal matrix is sometimes called a scaling matrix, since matrix multiplication with it results in changing scale (size). Its determinant is the product of its diagonal values. Definition As stated above, a diagonal matrix is a matrix in which all off-diagonal entries are zero. That is, the matrix with ''n'' columns and ''n'' rows is diagonal if \forall i,j \in \, i \ne j \implies d_ = 0. However, the main diagonal entries are unrestricted. The term ''diagonal matrix'' ma ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Band Matrix
Band or BAND may refer to: Places *Bánd, a village in Hungary * Band, Iran, a village in Urmia County, West Azerbaijan Province, Iran * Band, Mureș, a commune in Romania *Band-e Majid Khan, a village in Bukan County, West Azerbaijan Province, Iran People * Band (surname), various people with the surname Arts, entertainment, and media Music *Musical ensemble, a group of people who perform instrumental or vocal music **Band (rock and pop), a small ensemble that plays rock or pop **Concert band, an ensemble of woodwind, brass, and percussion instruments **Dansband, band playing popular music for a partner-dancing audience **Jazz band, a musical ensemble that plays jazz music **Marching band, a group of instrumental musicians who generally perform outdoors **School band, a group of student musicians who rehearse and perform instrumental music * The Band, a Canadian-American rock and roll group ** ''The Band'' (album), The Band's eponymous 1969 album * "Bands" (song), by American r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sylvester's Law Of Inertia
Sylvester's law of inertia is a theorem in matrix algebra about certain properties of the coefficient matrix of a real quadratic form that remain invariant under a change of basis. Namely, if ''A'' is the symmetric matrix that defines the quadratic form, and ''S'' is any invertible matrix such that ''D'' = ''SAS''T is diagonal, then the number of negative elements in the diagonal of ''D'' is always the same, for all such ''S''; and the same goes for the number of positive elements. This property is named after James Joseph Sylvester who published its proof in 1852. Statement Let ''A'' be a symmetric square matrix of order ''n'' with real entries. Any non-singular matrix ''S'' of the same size is said to transform ''A'' into another symmetric matrix , also of order ''n'', where ''S''T is the transpose of ''S''. It is also said that matrices ''A'' and ''B'' are congruent. If ''A'' is the coefficient matrix of some quadratic form of R''n'', then ''B'' is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
