Essentially, I am supposed to count how many operations a particular computational algorithm involves, and I've gotten stuck on this one part. My understanding is that for two nxn matrices, matrix multiplication requires of order $0(n^3)$ operations.
If P is a permutation matrix, and we also know the particular permutation that it represents, how many operations does P*A involve?
I'm assuming that it's of order $0(n)$? Or maybe even none (say, if the permutation simply involves storing the values differently - switching which values are in which columns)?
Can someone confirm this?
For an $n \times 1$ vector $v$ and $n \times n$ matrix $A$, to get the first entry of the resulting vector $Av$ you require $n$ multiplications and $n-1$ additions. Doing this for each ot the $n$ rows (entries), you get $n(n+n-1) \sim O(n^2)$ operations. Matrix multiplication is just $Av$ done for each of the $n$ columns $v$ of the second matrix, so the resulting operation count is $O(n^3)$, as you said.
However, in your case, multiplying on the left by $P$ corresponds to permuting the rows of $A$. In other words, if $P$ represents the permutation $\sigma \in S_n$, $\sigma : \{1,\dots,n\} \rightarrow \{1,\dots,n\}$, then the resulting matrix $PA$ has entries $a(\sigma(i),j)$, where $a(i,j)$ is the $i,j$ entry of $A$. Depending on the language you are using and how you code this, this should take no time at all.