How do we determine if a certain physical quantity is a vector? For instance in Newtonian physics we treat position of objects, displacements, velocities, forces, momenta, angular velocities etc all as vector quantities (little arrows in space which have a certain direction & magnitude that can be added using the parallelogram law of vector addition & can be multiplied by scalars). 
But who said that these physical quantities can be modelled using vector algebra? Is this an empirical statement or is there a theoretical reasoning behind it?
For instance why do velocities add linearly in Newtonian Mechanics? If an object is given a velocity of 10m/s North & a velocity of 10m/s East, then according to what I've been taught, the 2 velocities will just add like vectors to give the net velocity of the object but I don't see how this statement is obvious in any way? Is there a deeper reason for why velocity ought to behave like a vector in Euclidean Space? 
Moreover as I understand it, the vectors used in Newtonian Mechanics are vectors in 3 dimensional Euclidean Space whereas in relativity theory (where velocities don't add linearly) we use four vectors in an different abstract space, right? If relativity is the more fundamental theory, then why is it that these four vectors in abstract space behave like Euclidean vectors in real space for low velocities? Where's the connection?
When can we use vector algebra to model physical quantities? There are about 5 different definitions of vectors that I've encountered so far. How do we formally define vectors in physics?
Please be as elaborate as possible.  
 A: 
How do we formally define vectors in physics?

An excerpt from chapter one, page 12 of "Mathematics of Classical and Quantum Physics"

Originally, we introduced a vector as an ordered triple of numbers. 
  The rule for expressing the components of a vector in one coordinate
  system in terms of its components in another system tells us that if
  we fix our attention on a physical vector and we rotate the
  coordinate system, the vector will have different numerical components
  in the rotate coordinate system.
So we are led to realize that a vector is really more than an ordered
  triple.  Rather, it is many sets of ordered triples which are related
  in a definite way.  One specifies a vector by giving three ordered
  numbers, but these numbers are distinguished from an arbitrary
  collection of three numbers by including the law of transformation
  under rotation of the coordinate frame as part of the definition. 
  This law tells how all vectors change if the coordinate system
  changes.
Thus, one physical vector may be represented by infinitely many
  ordered triples.  The particular triple depends on the orientation of
  the coordinate system of the observer.  This is important because
  physical results must be the same regardless of one's vantage point,
  that is, regardless of the orientation of one's coordinate system.
This will be the case if a given physical law involves vectors on both
  sides of the equation.  Now, from this point of view, the
  transformation rule and the orthogonality relations may be used to
  define vectors.

A: A physical quantity is a vector if it transforms in the same way as a position vector when the coordinate system undergoes a transformation.
A: My intuitive answer is vectors are something with Vector additions and scalar multiplications.
Looking up my a textbook in algebra I think a more mathematician acceptable answer is 'vector space is a set, whose element can add together and multiplied by numbers. Vectors are the element of such set. The addition and multiplications must obey the following rules: (the exact phrasing is copied from Wikipedia: vector space)


*

*Associativity of vector addition: u + (v + w) = (u + v) + w

*Commutativity of vector addition: u + v = v + u

*Identity element of vector addition: There exists an element 0 ∈ V, called the zero vector, such that v + 0 = v for all v ∈ V.

*Inverse elements of vector addition: For every v ∈ V, there exists an element −v ∈ V, called the additive inverse of v, such that v + (−v) = 0.

*Compatibility of scalar multiplication with field multiplication: a(bv) = (ab)v

*Identity element of scalar multiplication: 1v = v, where 1 denotes the multiplicative identity in F.

*Distributivity of scalar multiplication with respect to vector addition: a(u + v) = au + av   

*Distributivity of scalar multiplication with respect to field addition: (a + b)v = av + bv
'


So vectors are elements in vector space, you speak about Euclidean vectors, that is great! which means you observed that definitions of vectors changed as space changed. I don't know if that answers your question 'why do velocities add linearly in Newtonian Mechanics'. I think the reasoning is not 'velocities add linearly', its the other way around: we find that velocities add up, and can be multiplied by a number. And this 2 operation satisfied the 8 rules above, so we decided to use a vector space to describe those relations. As Physicists we simply borrows this mathematical tool to model something, like directions, force etc.
For more place refer to Wikipedia: vector space https://en.wikipedia.org/wiki/Vector_space or try a linear algebra textbook or open-course.
I don't know if my understanding is correct or of any help, still thanks for reading.
