Bijective Functions: The Perfect Correspondence
Bijective Functions: The Perfect Correspondence
20 min read
Bijective functions are the mathematical gold standard for “perfect matching”—every input maps to a unique output, and every output comes from exactly one input. This seemingly simple concept underlies invertibility in linear algebra, coordinate transformations in computer graphics, cryptographic systems, and much more.
Related Posts:
- Matrix Determinants and Leibniz Theorem - Determinants determine if linear transformations are bijective
- Symmetric Groups: Understanding Permutations from First Principles - Permutations are bijective functions from a set to itself
- Signed Volume: Geometric Interpretation - Non-zero determinant means bijective transformation
- From Gradients to Hessians - Invertibility of the Hessian in optimization
Table of Contents
- What is a Bijective Function?
- Building Blocks: Injective and Surjective
- Why Bijections Matter
- Detecting Bijections
- Linear Algebra Connection
- Computer Vision Applications
- Common Pitfalls
- Interactive Examples
What is a Bijective Function?
A function $f: A \to B$ is bijective (or a bijection) if it establishes a perfect one-to-one correspondence between sets $A$ and $B$.
Formal Definition:
\[f \text{ is bijective} \iff f \text{ is both injective and surjective}\]Intuitive Definition:
- Every element in $A$ maps to exactly one element in $B$ (that’s just being a function)
- Every element in $B$ is the image of exactly one element in $A$ (that’s the bijection part)
Visual Metaphor: Think of a bijection as a perfect pairing dance where:
- Every person from group $A$ dances with exactly one person from group $B$
- Every person from group $B$ dances with exactly one person from $A$
- No one sits out, no one dances with multiple partners
Building Blocks: Injective and Surjective
A bijection is built from two properties:
1. Injective (One-to-One)
Definition: Different inputs produce different outputs.
\[f \text{ is injective} \iff \forall x_1, x_2 \in A: f(x_1) = f(x_2) \implies x_1 = x_2\]Contrapositive Form (often easier to use):
\[x_1 \neq x_2 \implies f(x_1) \neq f(x_2)\]Examples:
✅ Injective: $f(x) = 2x$ (doubling never produces the same output from different inputs)
\[f(2) = 4, \quad f(3) = 6 \quad (\text{different inputs} \to \text{different outputs})\]❌ Not Injective: $f(x) = x^2$ on $\mathbb{R}$ (both $2$ and $-2$ map to $4$)
\[f(2) = 4, \quad f(-2) = 4 \quad (\text{different inputs} \to \text{same output})\]Geometric Test: The horizontal line test. If any horizontal line intersects the graph more than once, the function is not injective.
Why It Matters: Injective functions are left-invertible. If $f$ is injective, we can define a left inverse $g$ on the range of $f$ such that $g(f(x)) = x$.
2. Surjective (Onto)
Definition: Every element in the codomain $B$ is “hit” by some element in the domain $A$.
\[f \text{ is surjective} \iff \forall y \in B, \exists x \in A: f(x) = y\]Examples:
✅ Surjective: $f: \mathbb{R} \to \mathbb{R}$, $f(x) = x^3$ (every real number has a cube root)
\[\text{For any } y \in \mathbb{R}, \text{ we can find } x = \sqrt[3]{y} \text{ such that } f(x) = y\]❌ Not Surjective: $f: \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$ (negative numbers are never outputs)
\[\text{No } x \in \mathbb{R} \text{ satisfies } f(x) = -1\]Why It Matters: Surjective functions are right-invertible. If $f$ is surjective, we can define a right inverse $h$ such that $f(h(y)) = y$ (though the choice might not be unique).
3. Bijective = Injective + Surjective
When $f$ is both injective and surjective, we get the best of both worlds:
\[\boxed{f \text{ is bijective} \iff f \text{ has a unique two-sided inverse } f^{-1}}\]Key Property:
\[f^{-1}(f(x)) = x \quad \forall x \in A\] \[f(f^{-1}(y)) = y \quad \forall y \in B\]Why Bijections Matter
1. Invertibility
Theorem: A function $f: A \to B$ has an inverse $f^{-1}: B \to A$ if and only if $f$ is bijective.
Proof Sketch:
- ($\Rightarrow$) If $f^{-1}$ exists:
- Injective: Suppose $f(x_1) = f(x_2)$. Then $x_1 = f^{-1}(f(x_1)) = f^{-1}(f(x_2)) = x_2$.
- Surjective: For any $y \in B$, let $x = f^{-1}(y)$. Then $f(x) = f(f^{-1}(y)) = y$.
- ($\Leftarrow$) If $f$ is bijective:
- For each $y \in B$, there exists exactly one $x \in A$ with $f(x) = y$ (surjective + injective).
- Define $f^{-1}(y) = x$. This is well-defined and is the inverse of $f$.
Why This Matters:
- Coordinate transformations: We can convert between different coordinate systems (world $\leftrightarrow$ camera $\leftrightarrow$ pixel)
- Cryptography: Encryption must be bijective to be reversible (decryption)
- Data structures: Hash functions try to be “almost injective” to avoid collisions
- Optimization: Invertible Hessian means we can find unique critical points
2. Cardinality
| Theorem: Two sets $A$ and $B$ have the same cardinality ($ | A | = | B | $) if and only if there exists a bijection $f: A \to B$. |
Examples:
Finite Sets: \(|A| = |B| = n \iff \text{there are } n! \text{ bijections between them}\)
Infinite Sets:
- $\mathbb{N}$ (natural numbers) and $\mathbb{Z}$ (integers) have the same cardinality (both countably infinite)
- Bijection: $f: \mathbb{N} \to \mathbb{Z}$ defined by $f(n) = \begin{cases} n/2 & \text{if } n \text{ even} \ -(n+1)/2 & \text{if } n \text{ odd} \end{cases}$
Computer Science: This is the foundation of counting arguments and complexity theory.
3. Structure Preservation
Bijections that preserve additional structure are called isomorphisms:
Linear Algebra: A bijective linear map $T: V \to W$ is a linear isomorphism.
\[T(\alpha \mathbf{v}_1 + \beta \mathbf{v}_2) = \alpha T(\mathbf{v}_1) + \beta T(\mathbf{v}_2)\]Group Theory: A bijective homomorphism $\phi: G \to H$ is a group isomorphism.
\[\phi(g_1 \cdot g_2) = \phi(g_1) \cdot \phi(g_2)\]Why This Matters: Isomorphic structures are “the same” for all practical purposes—they have identical properties, just with different labels.
Detecting Bijections
Method 1: Direct Verification
Step 1: Check injectivity
- Assume $f(x_1) = f(x_2)$ and prove $x_1 = x_2$
Step 2: Check surjectivity
- For arbitrary $y \in B$, solve $f(x) = y$ for $x \in A$
Example: $f: \mathbb{R} \to \mathbb{R}$, $f(x) = 3x + 5$
Injectivity: \(f(x_1) = f(x_2) \implies 3x_1 + 5 = 3x_2 + 5 \implies 3x_1 = 3x_2 \implies x_1 = x_2 \quad \checkmark\)
Surjectivity: \(\text{Given } y \in \mathbb{R}, \text{ solve } 3x + 5 = y \implies x = \frac{y - 5}{3} \in \mathbb{R} \quad \checkmark\)
Conclusion: $f$ is bijective, with inverse $f^{-1}(y) = \frac{y-5}{3}$.
Method 2: Construct the Inverse
If you can explicitly construct an inverse function $g: B \to A$ and verify that:
\[g(f(x)) = x \quad \forall x \in A\] \[f(g(y)) = y \quad \forall y \in B\]Then $f$ is automatically bijective.
Example: $f(x) = e^x$ from $\mathbb{R}$ to $(0, \infty)$
Inverse: $g(y) = \ln(y)$
Verify: \(g(f(x)) = \ln(e^x) = x \quad \checkmark\)
\[f(g(y)) = e^{\ln y} = y \quad \checkmark\]Method 3: Composition
Theorem: The composition of bijections is a bijection.
\[f: A \to B \text{ and } g: B \to C \text{ both bijective} \implies g \circ f: A \to C \text{ bijective}\]Inverse Property:
\[(g \circ f)^{-1} = f^{-1} \circ g^{-1}\]Note the reversed order!
Linear Algebra Connection
Bijective Linear Maps
Theorem: A linear map $T: \mathbb{R}^n \to \mathbb{R}^n$ represented by matrix $A$ is bijective if and only if:
\[\det(A) \neq 0\]Why This Works:
- $\det(A) \neq 0$ means the matrix is invertible
- Invertible linear maps are precisely the bijective ones
- The inverse matrix $A^{-1}$ represents $T^{-1}$
Geometric Interpretation:
\[|\det(A)| = \text{volume scaling factor}\]- $\det(A) \neq 0$: Transformation preserves dimensionality (bijective)
- $\det(A) = 0$: Transformation collapses space (not injective, not surjective)
Example:
\[A = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}, \quad \det(A) = 2 \cdot 1 - 1 \cdot 1 = 1 \neq 0\]So $T(\mathbf{x}) = A\mathbf{x}$ is bijective, with inverse:
\[A^{-1} = \begin{bmatrix} 1 & -1 \\ -1 & 2 \end{bmatrix}\]Rank-Nullity Theorem
Theorem: For a linear map $T: \mathbb{R}^n \to \mathbb{R}^m$ with matrix $A$:
\[\text{rank}(A) + \text{nullity}(A) = n\]Where:
- $\text{rank}(A) = \dim(\text{range}(T))$
- $\text{nullity}(A) = \dim(\ker(T))$
Bijection Criteria (when $n = m$):
\[T \text{ is bijective} \iff \text{rank}(A) = n \iff \text{nullity}(A) = 0 \iff \det(A) \neq 0\]Why:
- Injective: $\ker(T) = {\mathbf{0}}$ (nullity = 0)
- Surjective: $\text{range}(T) = \mathbb{R}^n$ (rank = $n$)
Jacobian Matrix
For a differentiable function $\mathbf{f}: \mathbb{R}^n \to \mathbb{R}^n$, the Jacobian matrix $J_{\mathbf{f}}(\mathbf{x})$ represents the local linear approximation:
\[J_{\mathbf{f}}(\mathbf{x}) = \begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \cdots & \frac{\partial f_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial x_1} & \cdots & \frac{\partial f_n}{\partial x_n} \end{bmatrix}\]Inverse Function Theorem: If $\det(J_{\mathbf{f}}(\mathbf{a})) \neq 0$ at a point $\mathbf{a}$, then $\mathbf{f}$ is locally invertible near $\mathbf{a}$.
Computer Vision Example: Camera calibration
\[\mathbf{f}: \text{(3D world coordinates)} \to \text{(2D pixel coordinates)}\]If the Jacobian is full rank, we can locally recover 3D position from 2D observations (up to scale).
Computer Vision Applications
1. Homogeneous Coordinates
In projective geometry, we use homogeneous coordinates to represent points:
\[\mathbb{R}^2 \to \mathbb{P}^2: \quad (x, y) \mapsto [x : y : 1]\]The projection $\mathbb{P}^2 \to \mathbb{R}^2$ is:
\[[x : y : w] \mapsto \left(\frac{x}{w}, \frac{y}{w}\right) \quad (w \neq 0)\]Is this bijective?
- Not injective: $[x : y : w]$ and $[\lambda x : \lambda y : \lambda w]$ map to the same point
- Not surjective: Points with $w = 0$ (points at infinity) have no preimage in $\mathbb{R}^2$
However, there’s a bijection between $\mathbb{P}^2 \setminus {w=0}$ and $\mathbb{R}^2$!
2. Warping and Transformations
Affine Transformation: $T: \mathbb{R}^2 \to \mathbb{R}^2$
\[T(\mathbf{x}) = A\mathbf{x} + \mathbf{b}\]Bijective if and only if $\det(A) \neq 0$.
Applications:
- Image rectification: Correcting perspective distortion
- Panorama stitching: Mapping images to a common coordinate frame
- Depth estimation: Triangulation requires bijective camera projections
Non-bijective transformations (problematic):
- Projection: 3D $\to$ 2D (not injective—depth information is lost)
- Chromatic correction: If two colors map to the same output (not injective—can’t invert)
3. Optical Flow
Optical flow estimates pixel displacement between frames:
\[I(x, y, t) = I(x + u, y + v, t + 1)\]Where $(u, v)$ is the flow vector.
Bijection Assumption: Pixels in frame $t$ have a unique correspondence in frame $t+1$ (one-to-one mapping).
Violations:
- Occlusions: Some pixels in frame $t$ are hidden in frame $t+1$ (not surjective)
- Disocclusions: New pixels appear in frame $t+1$ (not injective from the reverse perspective)
Modern Deep Learning: Networks learn bijective or “almost bijective” mappings for:
- Image-to-image translation (pix2pix, CycleGAN)
- Style transfer
- Super-resolution
Common Pitfalls
Pitfall 1: Confusing Injective and Surjective
❌ Wrong: “The function covers the whole codomain, so it’s injective.”
✅ Correct: That’s surjective, not injective.
Mnemonic:
- In-jective: Different inputs stay in their own separate outputs (one-to-one)
- Sur-jective: Outputs sur-round (cover) the entire codomain (onto)
Pitfall 2: Forgetting the Codomain
A function’s surjectivity depends on its codomain, not just its formula!
Example: $f(x) = x^2$
- $f: \mathbb{R} \to \mathbb{R}$ is not surjective (negative numbers aren’t hit)
- $f: \mathbb{R} \to [0, \infty)$ is surjective (every non-negative number is hit)
Always specify both domain and codomain: $f: A \to B$.
Pitfall 3: Assuming Local $\implies$ Global
A function can be locally bijective without being globally bijective.
Example: $f(x) = \sin(x)$ on $\mathbb{R}$
- Locally bijective near $x = 0$ (strictly increasing in $(-\pi/2, \pi/2)$)
- Not globally bijective (periodic, so not injective over all $\mathbb{R}$)
Solution: Restrict the domain to $[-\pi/2, \pi/2]$ to get a bijection onto $[-1, 1]$.
Pitfall 4: Ignoring Dimensions
For linear maps $T: \mathbb{R}^n \to \mathbb{R}^m$:
- If $n < m$: Cannot be surjective (not enough inputs to cover all outputs)
- If $n > m$: Cannot be injective (pigeonhole principle—some outputs must repeat)
- If $n = m$: Can be bijective (if $\det(A) \neq 0$)
Computer Vision: This is why 3D $\to$ 2D projection is inherently not bijective (information loss).
Interactive Examples
Example 1: Linear Function
Function: $f(x) = 2x - 3$
Domain: $\mathbb{R}$, Codomain: $\mathbb{R}$
Check Injectivity:
\[f(x_1) = f(x_2) \implies 2x_1 - 3 = 2x_2 - 3 \implies 2x_1 = 2x_2 \implies x_1 = x_2 \quad \checkmark\]Check Surjectivity:
\[\text{Given } y \in \mathbb{R}, \text{ solve } 2x - 3 = y \implies x = \frac{y + 3}{2} \in \mathbb{R} \quad \checkmark\]Conclusion: Bijective, with $f^{-1}(y) = \frac{y+3}{2}$.
Example 2: Quadratic Function
Function: $f(x) = x^2$
Case 1: $f: \mathbb{R} \to \mathbb{R}$
- Not injective: $f(2) = f(-2) = 4$
- Not surjective: No $x$ satisfies $x^2 = -1$
- Not bijective
Case 2: $f: [0, \infty) \to [0, \infty)$
- Injective: For $x_1, x_2 \geq 0$, $x_1^2 = x_2^2 \implies x_1 = x_2$ ✓
- Surjective: For any $y \geq 0$, $x = \sqrt{y}$ satisfies $x^2 = y$ ✓
- Bijective, with $f^{-1}(y) = \sqrt{y}$
Lesson: Restrict domain and codomain appropriately!
Example 3: Matrix Transformation
Transformation: $T(\mathbf{x}) = A\mathbf{x}$ where
\[A = \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}\]Compute Determinant:
\[\det(A) = 1 \cdot 4 - 2 \cdot 2 = 0\]Conclusion: Not bijective.
Why Not Injective: $\ker(A) \neq {\mathbf{0}}$
\[A \begin{bmatrix} 2 \\ -1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}\]So different inputs (like $\mathbf{x}$ and $\mathbf{x} + \begin{bmatrix} 2 \ -1 \end{bmatrix}$) give the same output.
Why Not Surjective: $\text{range}(A)$ is only 1-dimensional (the span of $\begin{bmatrix} 1 \ 2 \end{bmatrix}$), so most vectors in $\mathbb{R}^2$ are not hit.
Summary
Key Takeaways
- Bijective = Injective + Surjective
- One-to-one correspondence
- Unique inverse exists
- Invertibility Criterion:
- Functions: Bijective $\iff$ invertible
- Linear maps: $\det(A) \neq 0 \iff$ bijective
- Applications:
- Coordinate transformations (graphics, vision)
- Cryptography (reversible encryption)
- Cardinality (counting infinite sets)
- Optimization (Hessian invertibility)
- Detection Methods:
- Direct verification (injective + surjective)
- Construct inverse
- Check determinant (linear case)
- Common Mistakes:
- Confusing injective/surjective
- Ignoring codomain specification
- Assuming local $\implies$ global
- Dimensional mismatch
Visual Summary
Injective (One-to-One) Surjective (Onto) Bijective (Perfect Match)
A → B A → B A ↔ B
1 → a 1 → a 1 ↔ a
2 → b 2 → b 2 ↔ b
3 → c 3 → c 3 ↔ c
4 → d 4 ┘
e
Different inputs → All outputs hit Both properties
different outputs → Invertible!
Further Reading
Foundations:
- Halmos, P. R. Naive Set Theory (1960) - Classic treatment of functions and bijections
- Herstein, I. N. Abstract Algebra (1996) - Isomorphisms and structure preservation
Linear Algebra:
- Axler, S. Linear Algebra Done Right (2015) - Invertibility and determinants
- Strang, G. Linear Algebra and Its Applications (2016) - Computational perspective
Computer Vision:
- Hartley & Zisserman. Multiple View Geometry (2004) - Projective transformations
- Szeliski, R. Computer Vision: Algorithms and Applications (2022) - Geometric transformations
Final Thought:
Bijections are everywhere in mathematics and computer science—they’re the functions that “play nicely” with structure, allow perfect reversibility, and enable us to say that two seemingly different objects are “really the same.” Understanding bijections deepens your intuition for invertibility, isomorphisms, and the fundamental question: When can we go backwards?
The determinant is the computational gatekeeper: $\det(A) \neq 0$ is linear algebra’s way of saying “yes, you can invert this—there’s a bijection here.” 🎯
If you found this helpful, check out the related posts on matrix determinants and signed volume to see how bijections connect to geometric transformations!