We measure the matter power spectrum from 31 Lyα spectra spanning the redshift range of 1.6-3.6. The optical depth, τ, for Lyα absorption of the intergalactic medium is obtained from the flux using the inversion method of Nusser & Haehnelt. The optical depth is converted to density by using a simple power-law relation, . The non-linear 1D power spectrum of the gas density is then inferred with a method that makes simultaneous use of the one- and two-point statistics of the flux and compared against theoretical models with a likelihood analysis. A cold dark matter model with standard cosmological parameters fits the data well. The power-spectrum amplitude is measured to be (assuming a flat Universe), , with α varying in the range of 1.56-1.8 with redshift. Enforcing the same cosmological parameters in all four redshift bins, the likelihood analysis suggests some evolution in the temperature-density relation and the thermal smoothing length of the gas. The inferred evolution is consistent with that expected if reionization of He ii occurred at . A joint analysis with the Wilkinson Microwave Anisotropy Probe results together with a prior on the Hubble constant as suggested by the Hubble Space Telescope key project data, yields values of Ω m and σ 8 that are consistent with the cosmological concordance model. We also perform a further inversion to obtain the linear 3D power spectrum of the matter density fluctuations.