'I have extracted mfcc coefficients for each song' ... I don't know what you mean by this. It's difficult to interpret. In a typical system computing MFCC features a framesize of 8ms - 32ms is used. The most common frame sizes used in communications system are 10ms and 20ms.
Assume a frame has Xms frame size then the window size is typically 2X ms. That is, if you use a 10ms frame, you'll compute the FFT of a 20ms window with each FFT computation having 10ms overlap. This filterbank is commonly referred to as the WOLA (Weighted Overlap and Add) or sometimes OLA (Overlap and Add) filterbank. You can read more here https://ccrma.stanford.edu/~jos/sasp/WOLA_Processing_Steps.html
Some examples of open source software which compute MFCC coefficients in the above manner include the HTK toolkit (http://htk.eng.cam.ac.uk/) and Voicebox (won't let me post the link as my reputation is too low). There are however many more, often times utilizing similar but different techniques.
I am assuming when you talk about creating a matrix of MFCC coefficients that you are creating an MxN matrix of real coefficients. Where M is the number of cepstral coefficients (13 is your suggestion but 24 is more typical) while N is the number of frames for a song of interest.
Some possible solutions (please keep in mind that I haven't done this and am 'shooting from the hip')
1.) Gaussian Mixture Models: Use a GMM classifier for each frame of cepstral coefficients. That is, for each column of your MxN matrix, you can compute a decision that classifies that frame as belonging to a particular class (e.g. rock, pop, classical, speech or noise). The final decision could be determined by selecting the most common classifier.
2.) Neural Networks: Similar to above, but use neural nets ...
3.) Mahalanobis Distance: Compute the mahalanobis distance between the matrix features and the mean/variance of the different classes your trying to detect.
4.) Many many more ...
Solutions 1 and 2 will some amplitude dependence unless you normalize the coefficients. You may want to experiment with different normalization techniques in your training/verification of these approaches.