Category:Reducible

This category contains results about Reducible.
Definitions specific to this category can be found in Definitions/Reducible.

Reducible Fraction

Let $q = \dfrac a b$ be a vulgar fraction.

Then $q$ is defined as being reducible if and only if $q$ is not in canonical form.

That is, if and only if there exists $r \in \Z: r \ne 1$ such that $r$ is a divisor of both $a$ and $b$.

Such a fraction can therefore be reduced by dividing both $a$ and $b$ by $r$.

Reducible Polynomial

Let $K$ be a field.

A reducible polynomial over $K$ is a nonconstant polynomial over $K$ that can be expressed as the product of two polynomials over $K$ of smaller degree.

Reducible Linear Representation

Let $\rho: G \to \GL V$ be a linear representation.

$\rho$ is reducible if and only if there exists a non-trivial proper vector subspace $W$ of $V$ such that:

$\forall g \in G: \map {\map \rho g} W \subseteq W$

That is, such that $W$ is invariant for every linear operator in the set $\set {\map \rho g: g \in G}$.

Reducible $G$-Module

Let $M$ be a $G$-module.

Then $M$ is reducible if and only if the corresponding linear representation is reducible.

Mapping Reducible, also known as Many-One Reducible

Let $\Sigma, \Sigma'$ be finite sets.

Let:

\(\ds L\)

\(\subseteq\)

\(\ds \Sigma^*\)

\(\ds L'\)

\(\subseteq\)

\(\ds \Sigma'^*\)

be sets of finite strings over $\Sigma$ and $\Sigma'$ respectively, where:

$\Sigma^*$ denotes the set of all finite strings over the alphabet $\Sigma$.

Let $f : \Sigma^* \to \Sigma'^*$ be a computable function such that, for all $w \in \Sigma^*$:

$w \in L \iff \map f w \in L'$

Then, $f$ is a mapping reduction from $L$ to $L'$.