It is difficult to get the analytic solution of difference equation by using traditional methods with computer. A linear method based on complete linear transformation for getting the analytic solution of difference equation is proposed in this paper. The idea of this new method is dimensionality reduction. The orders of the high-order difference equation are reduced through determinant calculation, and this process is repeated till the last analytic expression of the solution of the difference equation appears. In essence, this algorithm is a transformation of Z-transform method combined with linear algebra method. The linear property of this algorithm enables one to get analytic solution other than numerical solution of difference equations using computer.