I had a similar problem for a 24X24 symbolic matrix. Mathematica could not do it and I ended up using [Fermats][2] "Redrowech[]". It took only 30 seconds. 

The problem is, Fermat's interface is far from optimal and the coding in it is, lets say cumbersome. Here is how I approached it:

 1. Create Fermat input with Mathematica (define the array and the variables)
 2. Append the created file to "ferstart.txt"
 3. Call the "gate to fermat" interface from Mathematica to Fermat ([Link to Fermat FLINK][1])
 4. Run from Mathematica `FEval["Redrowech[yourMatrix]"]` and save the result

The routine I used is tailored towards my particular matrices and I am therefore reluctant to share it. But if you decide to go down that path and have troubles I might be able to help (e.g. the Makefile of gatetofermat needed some editing for my machine). 



  [1]: https://www.ttp.kit.edu/~asmirnov/FLink-Source.htm
  [2]: http://://home.bway.net/lewis/