For being invertible matrix , we require that the determinant of that matrix is non zero . In other words , for n * n matrix , the rank of the matrix needs to be n only.
This means that all the rows (or columns) of the matrix are linearly independent ; neither is linearly independent on the other.
So we proceed this way :
We pick the first column : Number of ways that the elements of this first column can take = 2n - 1 [ 1 is subtracted to exclude the case where all the entries are 0's ]
We pick the second column : Number of ways that the elements of this first column can take = 2n - 2 [ 2 is subtracted to take care of the fact that the second column is linearly independent of the previous one i.e. first column .As only 2 multiples are possible at this juncture hence 2 is subtracted ].
We pick the third column : Number of ways that the elements of this first column can take = 2n - 22 [ 22 linear combinations of the first two columns are possible to get the third column.Hence those cases are subtracted ].
Likewise for the fourth column , required number of ways = 2n - 23
Continuing in this manner , for nth column number of ways = 2n - 2n-1
Hence required number of matrices = Number of ways of picking element for each column of a matrix
= (2n - 1) (2n - 2) (2n - 22) ...........(2n - 2n-1)
Worth reading : https://math.stackexchange.com/questions/127489/number-of-invertible-0-1-matrices
