You didn't say how sparse the matrix was, or what form the non-zero elements take (integer in some range ? double float ? single float ?), or what operation(s) you want to perform on this matrix ?, or whether it's randomly sparse or something regular (diagonal, triangular, ...) ?

Using Perl arrays or hashes invokes some hefty overheads (particularly on 64-bit machine). So, assuming the matrix is sparse enough and the data small enough, I would be tempted to do a little Inline::C to manage the data structure, the form of which would depend on the sparseness and the required operations... I can also testify to Inline::C being reasonably straightforward to use, at least on Linux -- though I have recently managed it on Winders !