What is the mathematical nature of a rotation matrix? I have a naive question: what is the mathematical nature of a rotation matrix?
Is a rotation matrix a tensor ?
EDIT: if a rotation matrix is fundamentally a tensor, what is its (n, m) notation?
 A: Mathematicians and physicists have somewhat different language for talking about tensors, which can make things a bit confusing.
From the mathematicians view-point, at the beginning a tensor is an element
of some tensor product $V\otimes V \otimes \cdots \otimes V^* \otimes \cdots \otimes V^*$, where $V$ is a finite dimensional vector space (over $\mathbb R$, say, but other fields of scalars could also be used), and some number of copies of $V$ and $V^*$ (its dual) appear.  If there are $m$ copies of $V$ and $n$ copies of $V^*$, one might call this a tensor of type $(m,n)$.
If you take $m = n = 1$, you get just elements of $V\otimes V^*$, which are the same as endomorphisms of $V$, which (if you choose a basis for $V$) can be thought of as $n\times n$ matrices.  So matrices are tensors (of type $(1,1)$) , in this sense.

The above is not usually what physicists mean by a tensor (though it is related).
To first approximation, what a physicist means by a tensor is a tensor in the above sense, which depends on a point $p$, in other words, a tensor-valued function (on space, or the plane, or whatever physical set-up is relevant).
So a matrix-valued function would be an example of what a physicist might mean by a tensor.
But in physical situations, there is often the further complication that
the vector space $V$ also depends on the point $p$, and so really what a physicist would mean by a tensor is a tensor-valued function, where the vector space $V$ giving rise to the tensors also depends on $p$.

The basic example of a vector space that depends on a point is tangent space to $p$ (if $p$ is varying over a surface, say, or more generally over some manifold).  In mathematical terms, a varying collection of vector spaces is called a vector bundle, and this particular example is called the tangent bundle (of whatever surfaces, or manifold, we are considering).
So a physicist's tensor is what mathematicians would call often call a tensor field, i.e. if $\mathcal V$ is a vector bundle, then it is a section 
of $\mathcal V^{\otimes m} \otimes (\mathcal V^*)^{\otimes n}$ (for some $m$ and $n$).

One other complication in communication is that physicists and mathematicians often describe vector bundles in different terms.  A mathematician often thinks about the vector bundle as a certain structure, in fact a certain kind of manifold, and uses the language of manifolds and maps between them to talk about tensor fields.
But often physicists will work in local coordinates.  Then they can then trivialize the tangent bundle (basisally, give a basis), but they keep track of how the basis changes if they choose different coordinates.  Then giving a tensor field amounts to giving a matrix valued function of the local coordinates, and giving a rule for how this function should be rewritten (physicists will say "transforms") if you make a change of local coordinates.  

One last thing: often $V$ and $V^*$ can be identified, say by choosing an inner product on $V$.  If $V$ is actually the tangent bundle of a manifold, rather than just a single vector space, then  such an inner product is called a metric on the underlying manifold. 
If you choose an inner product/metric, then you can identify $V$ and $V^*$, and so identify tensors of type $(m,n)$ with tensors of type $(m+n,0)$.  This is sometimes call raising and lowering indices (because of the traditional way it is notated in local coordinates).
In this way, a tensor of type $(1,1)$ might also be viewed as a tensor of type $(2,0)$ instead. 
A: A physicist's two cents:
A tensor is simply an object that transforms under a change of coordinate system by a certain prescribed rule. It is certainly not true that not every matrix is a tensor. A rotation matrix is just a matrix representation of the rotation operator. What makes a matrix represent a tensor is all in the manner of transformation under a coordinate change.
For example, a rank-1 tensor (vector) $v_i$ would transform under a coordinate transform operator $O$ in the following manner (using Einstein summation convention):
$$
v'_i = O^j_i v_j
$$
Similarly a tensor of rank 2 (no special name for it) $T_{ij}$ would transform thus:
$$
T'_{ij} = O^p_i O^q_j T_{pq}
$$
If you look at the manner a rotation operator transforms, it looks identical to that of a rank-2 tensor. So a rotation matrix is a perfectly valid representation of a rank-2 tensor. 
A: I don't know much about tensors.  What little I have seen of them confuses me.  I'll answer your first question, which requires no knowledge of tensors.
A 2- or 3-dimensional real rotation matrix $A$ is a matrix that satisfies $A^T A = I$ and $\operatorname{det}(A) = 1$.  The first condition is called "orthongonality" and can be stated in several equivalent ways.  An orthogonal matrix must satisfy $\operatorname{det}(A) = \pm 1$.  If you don't impose the condition $\operatorname{det}(A) = 1$, you still get an isometry ($\|A\mathbf{x}\| = \|\mathbf{x}\|$ for any column vector $\mathbf{x}$, where $\|\cdot \|$ is Euclidean norm), but if $\operatorname{det}(A) = -1$, $A$ is actually a reflection matrix.
If $A$ is a square matrix satisfying $A^T A = I$ and $\operatorname{det}(A) = 1$, but $A$ is larger than 3-by-3, I'm not sure if people use the term "rotation matrix" or if the term is appropriate.  You could have two coordinates rotating around one axis, and the other two coordinates rotating around another axis, or something weird like that, so the word "rotation" might not make sense.
