Random matrices in coordinate independent way

Question

How to generate a random matrix in a basis independent way (so that the random distribution does not change if the coordinates are rotated)?

I am especially interested in generating random rotation maps (in matrix or any other form) in basis independent way, or at least independent of swapping every two unit vectors.

I am also especially interested in generating "small" random changes (so called mutations) of matrices.

---

Now (see the answers below) it is clear how to generate basis-independent random matrices (both small and big) and also basis independent rotation matrices.

Now the question: how to generate small (rotating to a small angle) rotation matrices, is also answered.

Are there faster algorithms?

Answer 1

If you generate all matrix entries to be i.i.d. Gaussian, then the probability of each column is only dependent on the column vector's Euclidean length, and the column vector lengths are preserved under orthogonal transformations, so this is one way to get a distribution invariant under coordinate rotations.

Answer 2

user2566092 has explained how to generate a general basis-independent random matrix.

A basis-independent rotation matrix can be generated from it by polar decomposition.

Answer 3

Now I've invented a way to generate "small" rotations:

1. Generate a Gaussian random matrix.

2. Add identity matrix multiplied with a big real number to it.

3. Decompose it as in my other answer. The resulting rotation will be small.