|
Schwartz–Zippel Lemma
In mathematics, the Schwartz–Zippel lemma (also called the DeMillo–Lipton–Schwartz–Zippel lemma) is a tool commonly used in probabilistic polynomial identity testing, i.e. in the problem of determining whether a given multivariate polynomial is the 0-polynomial (or identically equal to 0). It was discovered independently by Jack Schwartz, Richard Zippel, and Richard DeMillo and Richard J. Lipton, although DeMillo and Lipton's version was shown a year prior to Schwartz and Zippel's result. The finite field version of this bound was proved by Øystein Ore in 1922.Ö. Ore, Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I (1922), no. 7, 15 pages. Statement and proof of the lemma Theorem 1 (Schwartz, Zippel). ''Let'' : P\in F _1,x_2,\ldots,x_n/math> ''be a non-zero polynomial of total degree'' ''over a field F. Let S be a finite subset of F and let'' ''be selected at random independently and uniformly from S. Then'' : \Pr (r_1,r_2,\ldots,r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial Identity Testing
In mathematics, polynomial identity testing (PIT) is the problem of efficiently determining whether two multivariate polynomials are identical. More formally, a PIT algorithm is given an arithmetic circuit that computes a polynomial p in a field, and decides whether p is the zero polynomial. Determining the computational complexity required for polynomial identity testing is one of the most important open problems in algebraic computing complexity. Description The question "Does (x+y)(x-y) equal x^2 - y^2 \, ?" is a question about whether two polynomials are identical. As with any polynomial identity testing question, it can be trivially transformed into the question "Is a certain polynomial equal to 0?"; in this case we can ask "Does (x+y)(x-y) - (x^2 - y^2) = 0"? If we are given the polynomial as an algebraic expression (rather than as a black-box), we can confirm that the equality holds through brute-force multiplication and addition, but the time complexity of the brute-force ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Frobenius Endomorphism
In commutative algebra and field theory, the Frobenius endomorphism (after Ferdinand Georg Frobenius) is a special endomorphism of commutative rings with prime characteristic , an important class which includes finite fields. The endomorphism maps every element to its -th power. In certain contexts it is an automorphism, but this is not true in general. Definition Let be a commutative ring with prime characteristic (an integral domain of positive characteristic always has prime characteristic, for example). The Frobenius endomorphism ''F'' is defined by :F(r) = r^p for all ''r'' in ''R''. It respects the multiplication of ''R'': :F(rs) = (rs)^p = r^ps^p = F(r)F(s), and is 1 as well. Moreover, it also respects the addition of . The expression can be expanded using the binomial theorem. Because is prime, it divides but not any for ; it therefore will divide the numerator, but not the denominator, of the explicit formula of the binomial coefficients :\frac, if . Ther ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial Matrix
In mathematics, a polynomial matrix or matrix of polynomials is a matrix whose elements are univariate or multivariate polynomials. Equivalently, a polynomial matrix is a polynomial whose coefficients are matrices. A univariate polynomial matrix ''P'' of degree ''p'' is defined as: :P = \sum_^p A(n)x^n = A(0)+A(1)x+A(2)x^2+ \cdots +A(p)x^p where A(i) denotes a matrix of constant coefficients, and A(p) is non-zero. An example 3×3 polynomial matrix, degree 2: : P=\begin 1 & x^2 & x \\ 0 & 2x & 2 \\ 3x+2 & x^2-1 & 0 \end =\begin 1 & 0 & 0 \\ 0 & 0 & 2 \\ 2 & -1 & 0 \end +\begin 0 & 0 & 1 \\ 0 & 2 & 0 \\ 3 & 0 & 0 \endx+\begin 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \endx^2. We can express this by saying that for a ring ''R'', the rings M_n(R and (M_n(R)) /math> are isomorphic. Properties *A polynomial matrix over a field with determinant equal to a non-zero element of that field is called unimodular, and has an inverse that is also a polynomial matrix. Note that the only scal ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Edmonds Matrix
In graph theory, the Edmonds matrix A of a balanced bipartite graph G = (U, V, E) with sets of vertices U = \ and V = \ is defined by : A_ = \left\{ \begin{array}{ll} x_{ij} & (u_i, v_j) \in E \\ 0 & (u_i, v_j) \notin E \end{array}\right. where the ''x''ij are indeterminates. One application of the Edmonds matrix of a bipartite graph is that the graph admits a perfect matching if and only if the polynomial det(''A''ij) in the ''x''ij is not identically zero. Furthermore, the number of perfect matchings is equal to the number of monomials in the polynomial det(''A''), and is also equal to the permanent of A. In addition, rank of A is equal to the maximum matching size of G. The Edmonds matrix is named after Jack Edmonds. The Tutte matrix In graph theory, the Tutte matrix ''A'' of a graph ''G'' = (''V'', ''E'') is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once. If the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Block Matrix
In mathematics, a block matrix or a partitioned matrix is a matrix that is '' interpreted'' as having been broken into sections called blocks or submatrices. Intuitively, a matrix interpreted as a block matrix can be visualized as the original matrix with a collection of horizontal and vertical lines, which break it up, or partition it, into a collection of smaller matrices. Any matrix may be interpreted as a block matrix in one or more ways, with each interpretation defined by how its rows and columns are partitioned. This notion can be made more precise for an n by m matrix M by partitioning n into a collection \text, and then partitioning m into a collection \text. The original matrix is then considered as the "total" of these groups, in the sense that the (i, j) entry of the original matrix corresponds in a 1-to-1 way with some (s, t) offset entry of some (x,y), where x \in \text and y \in \text. Block matrix algebra arises in general from biproducts in categories of matrices ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bipartite Graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the ''parts'' of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets U and V may be thought of as a coloring of the graph with two colors: if one colors all nodes in U blue, and all nodes in V red, each edge has endpoints of differing colors, as is required in the graph coloring problem.. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color. One often writes G=(U,V,E) to denote a bipartite graph whose partition has the parts U and V, with E denoting ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pfaffian
In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, when applied to the coefficients of a skew-symmetric matrix, is called the Pfaffian of that matrix. The term Pfaffian was introduced by who indirectly named them after Johann Friedrich Pfaff. The Pfaffian (considered as a polynomial) is nonvanishing only for 2''n'' × 2''n'' skew-symmetric matrices, in which case it is a polynomial of degree ''n''. Explicitly, for a skew-symmetric matrix A, : \operatorname(A)^2=\det(A), which was first proved by , who cites Carl Gustav Jacob Jacobi, Jacobi for introducing these polynomials in work on Pfaffian system, Pfaffian systems of differential equations. Caley obtains this relation by specialising a more general result on matrices which deviate from skew symmetry only in the first row and the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Skew-symmetric Matrix
In mathematics, particularly in linear algebra, a skew-symmetric (or antisymmetric or antimetric) matrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition In terms of the entries of the matrix, if a_ denotes the entry in the i-th row and j-th column, then the skew-symmetric condition is equivalent to Example The matrix :A = \begin 0 & 2 & -45 \\ -2 & 0 & -4 \\ 45 & 4 & 0 \end is skew-symmetric because : -A = \begin 0 & -2 & 45 \\ 2 & 0 & 4 \\ -45 & -4 & 0 \end = A^\textsf . Properties Throughout, we assume that all matrix entries belong to a field \mathbb whose characteristic is not equal to 2. That is, we assume that , where 1 denotes the multiplicative identity and 0 the additive identity of the given field. If the characteristic of the field is 2, then a skew-symmetric matrix is the same thing as a symmetric matrix. * The sum of two skew-symmetric matrices is skew-symmetric. * A scala ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and only if the matrix is invertible and the linear map represented by the matrix is an isomorphism. The determinant of a product of matrices is the product of their determinants (the preceding property is a corollary of this one). The determinant of a matrix is denoted , , or . The determinant of a matrix is :\begin a & b\\c & d \end=ad-bc, and the determinant of a matrix is : \begin a & b & c \\ d & e & f \\ g & h & i \end= aei + bfg + cdh - ceg - bdi - afh. The determinant of a matrix can be defined in several equivalent ways. Leibniz formula expresses the determinant as a sum of signed products of matrix entries such that each summand is the product of different entries, and the number of these summands is n!, the factorial of (t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
If And Only If
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is biconditional (a statement of material equivalence), and can be likened to the standard material conditional ("only if", equal to "if ... then") combined with its reverse ("if"); hence the name. The result is that the truth of either one of the connected statements requires the truth of the other (i.e. either both statements are true, or both are false), though it is controversial whether the connective thus defined is properly rendered by the English "if and only if"—with its pre-existing meaning. For example, ''P if and only if Q'' means that ''P'' is true whenever ''Q'' is true, and the only case in which ''P'' is true is if ''Q'' is also true, whereas in the case of ''P if Q'', there could be other scenarios where ''P'' is true and ''Q'' is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tutte Matrix
In graph theory, the Tutte matrix ''A'' of a graph ''G'' = (''V'', ''E'') is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once. If the set of vertices is V = \ then the Tutte matrix is an ''n'' × ''n'' matrix A with entries : A_ = \begin x_\;\;\mbox\;(i,j) \in E \mbox ij\\ 0\;\;\;\;\mbox \end where the ''x''''ij'' are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables ''xij'', ''i < j'' ): this coincides with the square of the of the matrix ''A'' and is non-zero (as a polynomial) if and only if a perfect matching exists. (This polynomial is not the |
Perfect Matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly one edge in . A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true. For example, consider the following graphs: : In graph (b) there is a perfect matching (of size 3) since all 6 vertices are matched; in graphs (a) and (c) there is a maximum-cardinality matching (of size 2) which is not perfect, since some vertices are unmatched. A perfect matching is also a minimum-size edge cover. If there is a perfect matching, then both the matching number and the edge cover number equal . A perfect matching can only occur when the graph has an even num ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
