Isomorphism & similarity as equivalences
Mathematics is full of relations meaning "the same up to a change of presentation": graph isomorphism, matrix similarity B = P⁻¹AP, congruence of triangles. Each is an equivalence relation, and the proof always follows the same three moves — identity gives reflexivity, inverse gives symmetry, composition gives transitivity. The classes are precisely the objects classified "up to" that notion.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Reflexivity from the identityThe identity map or identity matrix witnesses that every object is equivalent to itself.
- Symmetry from inversesIf φ witnesses A ∼ B, then φ⁻¹ witnesses B ∼ A. This is why the witnesses must be invertible.
- Transitivity from compositionComposing two witnesses gives a witness for the outer pair, and the composition of invertible maps is invertible.
- Classify with invariantsTwo objects in the same class share every invariant — degree sequence, eigenvalues, determinant — so a differing invariant proves they are inequivalent.
Worked example
Show matrix similarity (A ∼ B iff B = P⁻¹AP for some invertible P) is an equivalence relation.
- Reflexive: take P = I, then I⁻¹AI = A, so A ∼ A.
- Symmetric: if B = P⁻¹AP then A = PBP⁻¹ = (P⁻¹)⁻¹B(P⁻¹), witnessed by P⁻¹.
- Transitive: if B = P⁻¹AP and C = Q⁻¹BQ then C = Q⁻¹P⁻¹APQ.
- And Q⁻¹P⁻¹ = (PQ)⁻¹, so C = (PQ)⁻¹A(PQ) with PQ invertible.
Answer. Similarity is an equivalence relation, with witnesses I, P⁻¹ and PQ for the three properties.
Where marks get dropped
These are the specific errors that cost credit on isomorphism & similarity as equivalences questions — QED's rubric penalises each of them separately.
- Forgetting to check that the witness is invertible. Without invertibility symmetry fails, and the relation is only a preorder.
- Assuming equal invariants imply equivalence. Two non-isomorphic graphs can share a degree sequence; invariants refute equivalence but rarely establish it.
- Confusing similarity with equality of matrices. Similar matrices represent the same linear map in different bases and are usually different matrices.
Practise this until it is automatic
Unlimited fresh questions
QED generates new isomorphism & similarity as equivalences problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Equivalence Relations mastery is tracked so you know when this is exam-ready.
Isomorphism & similarity as equivalences — frequently asked questions
Why are similar matrices "the same"?
They represent one linear map in two bases, so they share eigenvalues, determinant, trace and rank. Anything basis-independent is a similarity invariant.
Is graph isomorphism easy to decide?
No efficient general algorithm is known, though it is not believed NP-complete either — it sits in an unusual complexity limbo, with a quasi-polynomial algorithm due to Babai.
What does "classification up to isomorphism" mean?
Describing the equivalence classes — listing one representative of each. "There are 11 graphs on 4 vertices up to isomorphism" is a statement about the quotient set.
The rest of Equivalence Relations
Equivalence classes, partitions and quotient sets. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Verifying an equivalence relation
- 2Equivalence classes [a]
- 3The class–partition correspondence
- 4The quotient set A/∼
- 5Congruence mod n
- 6The kernel of a function as an equivalence
- 7Well-definedness of operations on classes
- 8Counting equivalence relations
- 9Equivalence closure of a relation
- 10Refinement of equivalence relations
- 11Intersections & unions of equivalence relations
- 12Bell numbers & counting partitions
- 13Isomorphism & similarity as equivalences
Ready to make isomorphism & similarity as equivalences exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →