A Permutation Matrix is a Square binary matrix that has exactly one Entry of 1 in each row and each column and 0s elsewhere. It is used to represent permutations in Linear Algebra, where Multiplying a matrix by a Permutation Matrix results in the Permutation of its rows or columns.