The main objective of this paper is to show the sum of positive integral powers say kth powers of first n-natural numbers coincides with a polynomial function of degree k+1 in n over natural numbers for any positive integer k. This has been an interesting problem to the mathematicians for decades. In this research article, the existence and uniqueness of the polynomial has been depicted with principles of Linear Algebra. Some astonishing results among the polynomial coefficients have been traced. Moreover the methods depicted here open a way to write a formula for sum of any positive integral powers of first n-natural numbers.