Parity of permutations, impossible puzzles and the magical determinant

This video explores the concept of permutation parity, a fundamental idea in mathematics with applications in puzzles like the 15 puzzle and the Rubik's Cube, as well as in the explicit formula for the determinant in linear algebra. A permutation involves shuffling a set of items, such as numbered tiles. The parity of a permutation is either odd or even, determined by the number of "inversions." An inversion occurs when a pair of tiles is in descending order. For example, if tile 7 is followed by tile 5, that's an inversion. These inversions can be visualized as crossings in a permutation diagram, where arrows connect initial positions to final tile positions. If arrows cross, it indicates an inversion. The identity permutation, where tiles are in their original order, has zero inversions and is thus an even permutation. A "swap" is a special type of permutation where only two tiles are interchanged. Swaps are always odd permutations, meaning they always result in an odd number of inversions. A crucial property of swaps is that performing a swap after any permutation always flips its parity. If the original permutation was even, a swap makes it odd, and vice versa. Any random permutation can be returned to the identity permutation by performing a series of swaps. The number of swaps required to do this always matches the parity of the original permutation. If the initial permutation is odd, it will take an odd number of swaps to return to the identity (an even permutation). Conversely, an even permutation will require an even number of swaps to return to the identity. This is because each swap flips the parity: odd -> even -> odd -> even, and so on. To go from an odd parity to an even parity, an odd number of flips (swaps) is needed. This principle extends to combining permutations. If you have two permutations in sequence, their combined parity follows a simple rule similar to arithmetic: even + even = even, even + odd = odd, odd + even = odd, and odd + odd = even. This means that if you combine two permutations, their parities effectively add up. For example, if you apply an odd permutation after an even one, the result is an odd permutation. The concept of permutation parity is particularly useful for analyzing permutation puzzles. The 15 puzzle, for example, consists of 15 numbered tiles and one empty square in a 4x4 grid. Moving a tile into the empty square is interpreted as a swap between the tile and a "ghost tile" (tile 16) representing the empty space. When the empty square starts and ends in the same position (e.g., the bottom-right corner), the total number of swaps made is always even. This can be visualized by imagining a checkerboard pattern on the grid; as the empty square moves, it alternates between "green" and "red" squares. To return to its starting color, it must have made an even number of moves. Since each move is a swap, and the puzzle starts from the identity (even) permutation, any solvable configuration of the 15 puzzle (where the empty square returns to its original spot) must be an even permutation. This implies that if you randomly arrange the tiles, you have a 50% chance of ending up with an odd permutation, which cannot be solved by legal moves. Similarly, the Rubik's Cube can be analyzed using permutation parity. A quarter turn of a face on a Rubik's Cube permutes both the corner pieces and the edge pieces. When considering the corner pieces alone, each quarter turn acts as an odd permutation. The same is true for the edge pieces; each quarter turn results in an odd permutation of the edges. Since both the corner and edge permutations are odd for a single quarter turn, their parities are linked. If a series of quarter turns results in an even permutation of the corners, it must also result in an even permutation of the edges, and vice-versa. This means that if you were to physically swap two corner pieces, or two edge pieces, the resulting cube would be unsolvable through normal rotations, because the parities of the corner and edge permutations would no longer be consistent. When considering all pieces (corners and edges) simultaneously, a quarter turn corresponds to an even overall permutation (odd + odd = even). This explains why certain scrambled Rubik's Cube configurations (e.g., those created by physically swapping pieces) are impossible to solve. Beyond puzzles, permutation parity is crucial in defining the determinant of a matrix. The determinant formula involves summing products of matrix entries, where each product corresponds to a permutation of column indices. Each term in the sum is multiplied by +1 if the corresponding permutation is even, and -1 if it is odd. This explicit formula, while complex for larger matrices, highlights the fundamental role of permutations and their parities in linear algebra. The proof that a swap flips parity can be visualized by considering two arrows in a permutation diagram that are about to be swapped. Initially, they either cross or don't. After the swap, their crossing status changes, adding or removing one crossing, thus changing the parity. Any interactions with other arrows in the diagram tend to add or remove an even number of crossings, thus not affecting the overall parity change caused by the initial single crossing change.