# Dimension and cardinality of vector spaces in Coding Theory

Let $$V$$ be a vector space over $$F$$, where $$\dim(V) = n$$. Then $$|V| = |F|^{n}$$. This is intuitive for me in abstract settings. Consider the standard basis for $$V$$, $$\{e_1,e_2,...,e_n\}$$. There are $$n$$ non-zero entries, and $$|F|$$ possible elements for each entry, so $$|V| = |F|^{n}$$.

I'm currently taking a coding theory course. Let $$C$$ be a $$q$$-ary linear code over $$F$$ (in other words $$|F| = q$$,) with dimension $$k$$ and length $$n$$. $$C$$ has a generator matrix $$G = \begin{bmatrix} c_{1}^{T} \\ c_{2}^{T} \\ \vdots \\ c_k^T \end{bmatrix} = \begin{bmatrix} c_{11} & c_{12} & \dots & c_{1n} \\ c_{21} & c_{22} & \dots & c_{2n} \\ \vdots \\ c_{k1} & c_{k2} & \dots & c_{kn} \\ \end{bmatrix}$$ which of course has the additional structure $$G = [I_{k}|A]$$.

Now, $$C \subseteq F^{n}$$. (I mean by $$F^{n}$$ the $$n$$-tuples of elements of $$F$$, sorry if that's not standard notation) Clearly $$|F^{n}| = |F|^{n} = q^{n}$$. $$C$$ also consists of $$n$$-tuples of elements of $$F$$, but not necessarily all of them.

I guess my question is can I apply the standard basis intuition I used in the abstract setting to linear codes? i.e although $$\{c_{1}^{T}, c_{2}^T, \dots, c_k^T\}$$ is a basis for $$C$$, can I choose a basis of $$k$$ vectors by taking $$e_1, \dots e_k$$ and extending them with 0's until they have length $$n$$? Maybe this isn't the exact technique needed but my idea is to construct some basis where there are $$k$$ non zero entries, 1 in each of the basis vectors. I'm confused because I have a $$k$$ dimensional vector space whose elements are vectors of length $$n$$.

Let me know if anything isn't clear, and thank you!

Edit: it is a given result in my book that $$|C| = q^{\dim(C)}$$, so I "know" the result and this post is an effort to better understand it.

You asked : can I choose a basis of $$k$$ vectors by taking $$e_1, \dots e_k$$ and extending them with 0's until they have length $$n$$?
No, you should not just fill up the remaining $$n-k$$ components just by zeros. The whole idea of the linear code is to to use the first $$k$$ components in each vector to encode information and to fill up the remaining $$n-k$$ components with redundant information.
If you would just choose the $$n-k$$ components to be always zero, then this would not result in a very smart usage of the redundant part. At least, when all $$n-k$$ should be always zero, and you would receive a vector having a non-zero in part where zeroes are expected, then you could conclude that some noise malformed the transmission.
• So in a generator matrix $G = [I_k|A]$, $I_k$ should contain encoded information while $A$ provides redundancy for error detecting and correction? Interesting and seems quite important haha. I'm not taking this course in my native language so I think some things are slipping past me. But in analyzing the cardinality of $C$, the naive basis I constructed by filling the $n-k$ remaining components with 0's is still a valid basis for $C$, correct? Although it's perhaps not a useful one. – CFlaherty Apr 23 '19 at 13:32
• Filling the $n-k$ components with $0$ is equivalent to having $A$ as $0$ matrix. In that way it fits in the framework you mentioned above. In this sense your question could be answered in an affirmative way. – Maksim Apr 23 '19 at 14:31