How to apply a permutation to a symmetric square matrix?

Question

Given a symmetric square matrix, how can I apply a permutation to the rows and columns (i.e. the same permutation to both the rows and the columns) such a way that the new structure of the matrix should follow the new row and column order?

Consider an order of rows/columns, according to which the elements of a set are arranged in a matrix:

order = Range[5];
matrix = Table[Subscript[a, i, j], {i, 5}, {j, 5}];
TableForm[matrix, TableHeadings -> {order, order}]

Now take a permutation of the row/column order:

newOrder = RandomSample[order]
(*
   ==> {1, 4, 5, 2, 3}
*)

FindPermutation finds the appropriate permutation cycle for the new order:

permutation = FindPermutation[order, newOrder]
Permute[order, permutation]
(*
   ==> Cycles[{{2, 4}, {3, 5}}]
   ==> {1, 4, 5, 2, 3}
*)

Now the question is: How to easily and elegantly apply the above permutation (preferably in its Cycles form) to the matrix to yield the following one:

Some notes:

• The matrix is always square and symmetric.
• Column and head orders are always identical.
• Bear in mind that order, and consequently matrix, can be big (e.g. 4^8 for order)
• Since matrix can be big, I'm looking for a method, that applies the permutation 'locally', that is without reconstructing the whole table every time, or without applying replacements/functions enumerating each element, thus no dispatch table should be used. This is rather important, as it could be that the new order only swaps two columns/rows, and nothing else.

Answer 1

How about:

ord = {1, 4, 5, 2, 3}
matrix[[ord, ord]]

(You can convert any permutation (including Cycles) to an index list using PermutationList.)