What should "The Fundamental Theorem of Linear Algebra" assert? Unlike some other basic fields of mathematics, linear algebra does not seem to have a universally agreed-upon fundamental theorem. This I imagine might be because the subject usually admits a lot of equivalent formulations to statements and it is perhaps hard (or pointless) to tell which are the fundamental ones and which are the consequences. Still, some of them might be arguably more natural or less constructed than others, so maybe there is some value in the question of what the "right" statement of the "key idea" of linear algebra should be, and it what sense it is fundamental? 
There is a vague entry on this on Wikipedia.
What I don't like about it most is simply that it is stated in terms of matrices, which I am accustomed to think of no more and no less than just convenient block notations to encode linear maps on finite-dimensional vector spaces (sure it could be rewritten in terms of linear maps, but do singular value decompositions really fit the above description?)
What rings truly fundamental to me is the statement that if $V, W$ are vector space, then any map defined on some basis of $V$ and with values in $W$ extends uniquely to a linear map on $V$ (and what's more, it is injective/surjective/bijective if and only if the system of image vectors is linearly independent/spanning/a basis). I've seen courses calling such a statement the fundamental theorem, a slogan and Lemma x.y, but it seems to me that this statement in particular (and the straightforward proofs of its sub-statements) make it beautifully clear how the concepts of linearity, basis, subspace etc. click.
What are people's thoughts on this?
EDIT: I agree that the dimension/basis existence theorem is perhaps the most fundamental statement we can make about vector spaces, but it seems to me that the righteous owner of such results is matroid theory. And what's more, this would mean that there is no linear algebra in a choice-free world. I think there is, in principle, nothing to stop us from thinking of linear algebra as being a theory of objects, which are pairs consisting of a vector space with some given basis - shouldn't the FTLA be a statement about such objects (and not care about basis existence in general)?
 A: For beginner Linear Algebra, some sources call the list of conditions for a matrix to be invertible the Fundamental Theorem of Linear Algebra.
http://mathworld.wolfram.com/InvertibleMatrixTheorem.html
A: I think that the fundamental theorem of linear algebra should be the unification of the dimension theorem and the fact that every vector space has a basis, namely:

Every vector space has a basis, and all bases of a vector space have the same cardinality.

This seems like one of the most fundamental statements we can make, as it allows us to talk about the dimension of a vector space. An extension of this could include the fact that if $ L $ is linearly independent and $ L \subseteq S $ spans, then there is a basis $ B $ such that $ L \subseteq B \subseteq S $.
If you are uncomfortable with the use of AC, then you may drop the first part of the theorem, and start by assuming that a basis exists.
A: The making of "fundamental theorems" is something quite outdated, and not really useful. The "fundamental" theorem of calculus is quite important, sure, but it received such name because it was the first time people realized the connection between derivation and integration. The "fundamental" theorem of algebra is also a major result (namely, that the field of complex numbers is algebraically closed), but is by no means a result people want to call "fundamental" anymore. There is really no use of choosing what the "fundamental" theorem of linear algebra should be, because there isn't really such a thing. The mindset of times when people named such theorems fundamental was quite different from what it is today! 
A: From the point of view of solving linear equations, the Fundamental Theorem of Linear Algebra might be the following restatement of the Rank-Nullity Theorem:

Theorem [FTLA]. Let $\mathbb{F}$ be a field and let $A = (u_1, \ldots, u_n)$ be an $m \times n$ matrix with entries in $\mathbb{F}$. There exists $r \in \mathbb{N}_0$, distinct columns $j_1,\ldots, j_r$ of $A$, and vectors $v_1, \ldots, v_{n-r} \in \mathbb{F}^n$ such that, if $b \in \mathbb{F}^m$ and $S = \{x \in \mathbb{F}^n : Ax = b\}$, then
  
  
*
  
*$S \not= \varnothing$ if and only if $b = \beta_1 u_{j_1} + \cdots + \beta_r u_{j_r}$ for some $\beta_1, \ldots, \beta_r \in \mathbb{F}$;
  
*if $x_0 \in S$ then $x \in S$ if and only if $x= x_0 + \gamma_1 v_1 + \cdots + \gamma_{n-r} v_{n-r}$  for some $\gamma_1, \ldots, \gamma_{n-r} \in \mathbb{F}$.

