Cannot install cudamat using setup.py. "nvcc not found", although this is in my PATH

Question

I am trying to install cudamat on an instance of Ubuntu 14.04 EC2 with Cuda installed.

The installation of the script failed to execute "cannot execute" nvcc ": there is no such file or directory". I added a line to display the $ PATH environment variable, which has no previously exported shell variables:

(deeplearning) ubuntu@ip-x-x-x-x:~/cudamat$ sudo python setup.py install
/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin running
install running bdist_egg running egg_info writing
cudamat.egg-info/PKG-INFO writing top-level names to
cudamat.egg-info/top_level.txt writing dependency_links to
cudamat.egg-info/dependency_links.txt reading manifest file
'cudamat.egg-info/SOURCES.txt' writing manifest file
'cudamat.egg-info/SOURCES.txt' installing library code to
build/bdist.linux-x86_64/egg running install_lib running build_py
running build_ext building 'cudamat.libcudamat' extension nvcc
-I/usr/include/python2.7 -c cudamat/cudamat.cu -o build/temp.linux-x86_64-2.7/cudamat/cudamat.o -O --ptxas-options=-v
--compiler-options=-fPIC unable to execute 'nvcc': No such file or directory error: command 'nvcc' failed with exit status 1

If anyone is interested, here is the export command from .bashrc:

export PATH=/usr/local/cuda-7.5/bin:/home/ubuntu/.virtualenvs/deeplearning/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games
export LD_LIBRARY_PATH=/usr/local/cuda-7.5/lib64:

I checked that my path is set:

(deeplearning) ubuntu@ip-x-x-x-x:~/cudamat$ env
LD_LIBRARY_PATH=/usr/local/cuda-7.5/lib64
PATH=/home/ubuntu/.virtualenvs/deeplearning/bin:/usr/local/cuda-7.5/bin:/home/ubuntu/.virtualenvs/deeplearning/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games