Can You Pray without a Prayer Mat?
Question

What is the ruling on praying on prayer mats? What is the ruling on putting a prayer mat in the mosque for the imam to pray on? Is this bid`ah? May Allah reward you with good.
Praise be to Allah.Offering prayer on a prayer mat
Offering prayer on a prayer mat is permissible in principle. Al-Bukhari (379) and Muslim (513) narrated that Maymunah (may Allah be pleased with her) said: The Messenger of Allah (peace and blessings of Allah be upon him) used to pray on a khumrah. 
A khumrah is a small mat made of palm leaves that is big enough for the face, on which a worshipper may prostrate to protect himself from the heat or coldness of the ground. 
Al-Khattabi favoured the view that the khumrah may be bigger than that, and he quoted as evidence the report narrated by Abu Dawud (5247) from Ibn 'Abbas, who said: A mouse came and started dragging the wick of the lamp and threw it in front of the Messenger of Allah (peace and blessings of Allah be upon him), on the khumrah on which he was sitting, and it burned an area the size of a dirham… (This hadith was classed as sahih by al-Albani in Sahih Abi Dawud, 4369.) 
It says in ‘Awn al-Ma’bud: “This clearly shows that the word khumrah may apply to a large mat. This was also stated in al-Nihayah.” (See Fath al-Bari, 333) 
Al-Shawkani said: 
“This hadith indicates that there is nothing wrong with praying on a mat, regardless of whether it is made of rags, palm leaves or anything else, whether it is small or big, like a mat or carpet, because it is proven that the Prophet (peace and blessings of Allah be upon him) prayed on mats, carpets and animal pelts. 
Cases where it is not permissible to pray on carpets
But there may be some reasons why it is not permissible to pray on carpets and similar things. 
For example: 

If the carpet contains images of animate beings; in which case it is haram to keep them and the images must be blotted out. Please see question no. 12422 . 
If the carpet has decorations and patterns that attract the attention of the worshipper and distract him from his prayer; praying on such carpets is makruh.

The Standing Committee said: 
“With regard to pictures of inanimate objects such as mountains, rivers, lakes, plants, trees, houses and so on, so long as there are no images of living beings in or around them, these are permissible, but praying on them is makruh because they distract the worshipper and detract from his proper focus and humility (khushu’) in prayer, but his prayer is still valid.” (Fatawa al-Lajnah al-Daimah, 6/180)
They also said: 
“The mosques are the houses of Allah, built for the establishment of prayer and the glorification of Allah and the fear of Allah.  
Patterns and decorations in the furnishings and on the walls of the mosques are things that distract the heart from the remembrance of Allah and take away much of the worshippers’ proper focus and humility. Hence they were regarded as makruh by many of the salaf. So the Muslims should avoid that in their mosques and strive to make their worship perfect by keeping distractions away from the places in which they seek to draw close to Allah the Lord of the Worlds, hoping to increase their reward. But with regard to praying (on carpets decorated with such patterns ), it is valid.” 

If praying on the rug is done in order to avoid praying on the ground.

Al-Bukhari (2036) narrated that Abu Sa’id al-Khudri (may Allah be pleased with him) said: We observed i'tikaf with the Messenger of Allah (peace and blessings of Allah be upon him) during the middle ten days of Ramadan, and we came out on the morning of the twentieth. The Messenger of Allah (peace and blessings of Allah be upon him) addressed us on the morning of the twentieth and said: “I was shown Laylat al-Qadr but then I was made to forget it, so seek it in the last ten nights, on the odd-numbered nights. I saw that I was prostrating in water and mud. Whoever was observing i’tikaf with the Messenger of Allah (peace and blessings of Allah be upon him), let him go back.” So the people went back to the mosque, and we did not see any trace of a cloud in the sky. Then a cloud came and it rained, and the iqamah for prayer was given, and the Messenger of Allah (peace and blessings of Allah be upon him) prostrated in mud and water until we saw the marks of mud on the tip of his nose and his face. 
According to a report narrated by Muslim (1167): “And his forehead was covered with mud and water.” 
This hadith points to the humility of the Prophet (peace and blessings of Allah be upon him), as he prostrated on water and mud, and he did not order that something be brought for him to prostrate on. 

If praying on the rug is done to avoid praying on the carpets that are spread for all the people in the mosque, or if a person does that to be on the safe side because there may be some impurity (najasah) on the ground.

Shaykh al-Islam Ibn Taymiyah said: 
“With regard to those who suffer from extreme waswasah (whispers from the Shaytan), they do not pray on the ground or on the carpets spread out for everyone on the ground, rather they pray on a rug or something similar…” (Majmu’ al-Fatawa, 22/177) 

If a man seeks to pray on the rug because he thinks that it is essential to have a rug just for prayer and that he has to pray on something whether he is at home or in the mosque. Many people only ever pray on the rug even if the house is carpeted.

Shaykh al-Islam (may Allah have mercy on him) said: 
“Praying on rugs, in the sense that the worshipper insists on that – this was not the way of the salaf, the Muhajirin and Ansar and those who followed them in truth at the time of the Messenger of Allah. Rather they used to pray on the ground in his mosque, and none of them had a rug that was used just for prayer. It was narrated that when ‘Abd al-Rahman ibn Mahdi came to Madinah he spread out a rug, and Malik ordered that it be taken away. It was said to him, “He is ‘Abd al-Rahman ibn Mahdi.” Malik said, “Do you not know that spreading a rug in our mosque is bid’ah (an innovation)?”’ ( Majmu’ al-Fatawa, 22/163)

The same applies to the practice in many mosques of having a rug that is just for the imam, which is set out for him to pray on, even though the mosque is carpeted. Why is he distinguished from the other worshippers??

This is not appropriate because there is no need for it, and because that may make him feel somewhat superior to the people.
 The point is that putting down rugs in a carpeted mosque is a bid`ah unless there is a reason for that, such as it being very cold, or the floor being rough or the first carpet being impure or filthy, and so on.
And Allah knows best.