Prove $V$ over finite field of $q$ elements can be written as union of $q + 1$ proper subspaces
Let $V$ be a vector space (can be finite or infinite) over finite field $K$, such that $dim V > 1$ and $|K| = q < infty$. Prove there exist proper subspaces $V_0, dots, V_q$ such that $V = V_0 cup dots cup V_q$. I have no idea where to start from.
linear-algebra combinatorics vector-spaces finite-fields
asked Nov 23 '18 at 7:24
user4201961user4201961
699411
add a comment |
Let $V$ be a vector space (can be finite or infinite) over finite field $K$, such that $dim V > 1$ and $|K| = q < infty$. Prove there exist proper subspaces $V_0, dots, V_q$ such that $V = V_0 cup dots cup V_q$. I have no idea where to start from.
linear-algebra combinatorics vector-spaces finite-fields
asked Nov 23 '18 at 7:24
user4201961user4201961
699411
5
i'd do it first for $dim V=2$.
– Lord Shark the Unknown
Nov 23 '18 at 7:27
3
Pick two linearly independent maps $a, b : V to K$. For each $k in K$, let $V_k = left{v in V mid aleft(vright) = k bleft(vright)right}$. Also, let $V_infty = left{v in V mid bleft(vright) = 0 right}$. Then, $V = V_infty cup bigcup_{k in K} V_k$.
– darij grinberg
Nov 23 '18 at 18:23
add a comment |
Let $V$ be a vector space (can be finite or infinite) over finite field $K$, such that $dim V > 1$ and $|K| = q < infty$. Prove there exist proper subspaces $V_0, dots, V_q$ such that $V = V_0 cup dots cup V_q$. I have no idea where to start from.
linear-algebra combinatorics vector-spaces finite-fields
asked Nov 23 '18 at 7:24
user4201961user4201961
699411
Let $V$ be a vector space (can be finite or infinite) over finite field $K$, such that $dim V > 1$ and $|K| = q < infty$. Prove there exist proper subspaces $V_0, dots, V_q$ such that $V = V_0 cup dots cup V_q$. I have no idea where to start from.
linear-algebra combinatorics vector-spaces finite-fields
linear-algebra combinatorics vector-spaces finite-fields
asked Nov 23 '18 at 7:24
user4201961user4201961
699411
asked Nov 23 '18 at 7:24
user4201961user4201961
699411
edited Nov 23 '18 at 12:48
user593746
asked Nov 23 '18 at 7:24
user4201961user4201961
699411
asked Nov 23 '18 at 7:24
user4201961user4201961
699411
asked Nov 23 '18 at 7:24
user4201961user4201961
699411
699411
5
i'd do it first for $dim V=2$.
– Lord Shark the Unknown
Nov 23 '18 at 7:27
3
Pick two linearly independent maps $a, b : V to K$. For each $k in K$, let $V_k = left{v in V mid aleft(vright) = k bleft(vright)right}$. Also, let $V_infty = left{v in V mid bleft(vright) = 0 right}$. Then, $V = V_infty cup bigcup_{k in K} V_k$.
– darij grinberg
Nov 23 '18 at 18:23
add a comment |
5
i'd do it first for $dim V=2$.
– Lord Shark the Unknown
Nov 23 '18 at 7:27
3
Pick two linearly independent maps $a, b : V to K$. For each $k in K$, let $V_k = left{v in V mid aleft(vright) = k bleft(vright)right}$. Also, let $V_infty = left{v in V mid bleft(vright) = 0 right}$. Then, $V = V_infty cup bigcup_{k in K} V_k$.
– darij grinberg
Nov 23 '18 at 18:23
5
5
i'd do it first for $dim V=2$.
– Lord Shark the Unknown
Nov 23 '18 at 7:27
i'd do it first for $dim V=2$.
– Lord Shark the Unknown
Nov 23 '18 at 7:27
3
3
Pick two linearly independent maps $a, b : V to K$. For each $k in K$, let $V_k = left{v in V mid aleft(vright) = k bleft(vright)right}$. Also, let $V_infty = left{v in V mid bleft(vright) = 0 right}$. Then, $V = V_infty cup bigcup_{k in K} V_k$.
– darij grinberg
Nov 23 '18 at 18:23
Pick two linearly independent maps $a, b : V to K$. For each $k in K$, let $V_k = left{v in V mid aleft(vright) = k bleft(vright)right}$. Also, let $V_infty = left{v in V mid bleft(vright) = 0 right}$. Then, $V = V_infty cup bigcup_{k in K} V_k$.
– darij grinberg
Nov 23 '18 at 18:23
add a comment |
2 Answers
2
active
oldest
votes
We claim that if $V$ is a vector space over a finite field $K$ of order $q$ such that $dim V>1$, and $m$ is a non-negative integer, then $V$ can be written as a union of $m$ proper subspaces of $V$ if and only if $mgeq q+1$. (From the proof below, it also follows that if $K$ is not finite, then there is no way to cover a vector space $V$ over $K$ with $dim V>1$ by finitely many proper subspaces.)
First suppose that $mgeq q+1$. It suffices to assume that $m=q+1$. Pick a basis $mathcal{B}$ of $V$. Let $a,binmathcal{B}$ be two distinct elements (noting that $|mathcal{B}|>1$ since $dim V>1$). For each $kin K$, we define $V_k$ to be the span of ${a+kb}cupbig(mathcal{B}setminus{a,b}big)$, and $U$ is the span of $mathcal{B}setminus{a}$. Show that
$V=Ucup bigcup_{kin K}V_k$.
Conversely, suppose that $V$ can be written as a union of $m$ proper subspaces $W_1,W_2,ldots,W_m$ with $m$ being smallest possible (from the previous paragraph we know $m$ exists, so taking the smallest one is possible). It is easy to see that $m>1$. By minimality of $m$, for any $i$, we have $W_inotsubseteq bigcup_{jneq i}W_j$.
Take $uin W_1setminusbigcup_{jneq1}W_j$ and $vin W_2setminusbigcup_{jneq 2}W_j$. Since $u+svin V$ for all $sin K$ such that $sneq 0$, we must have $u+svin W_j$ for some $j$. We claim that the assignment $sin Ksetminus{0}$ to the smallest $j$ such that $u+svin W_j$ is an injective function from $Ksetminus{0}$ to ${3,4,ldots,m}$. From here, it follows that $$q-1=big|Ksetminus{0}big|leq big|{3,4,ldots,m}big|=m-2,$$
establishing our claim.
Now, to prove the assertion in the previous paragraph, we first note that $u+svnotin W_1$ and $u+svnotin W_2$ for $sne 0$. If $u+svin W_1$, then $v=s^{-1}big((u+sv)-ubig)in W_1$ since $uin W_1$, which is a contradiction. If $u+svin W_2$, then $u=(u+sv)-svin W_2$ since $vin W_2$, which is also a contradiction. So, $u+svin W_j$ for some $jin{3,4,ldots,m}$.
Now, suppose that there are two non-zero $s,tin K$ such that $u+sv$ and $u+tv$ are in the same $W_i$, where $iin{3,4,ldots,m}$. Then,
$$v=(s-t)^{-1}big((u+sv)-(u+tv)big)in W_i.$$
But $vin W_2setminus bigcup_{jneq 2}W_j$, so we have another contradiction. The assertion is now proven.
add a comment |
Hint: If $(x_1,x_2,ldots)in V$ then either $x_1=0$ or there exists $cin K$ with $x_2=cx_1$.
answered Nov 23 '18 at 7:43
Hagen von EitzenHagen von Eitzen
276k21269496
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3010079%2fprove-v-over-finite-field-of-q-elements-can-be-written-as-union-of-q-1-p%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
We claim that if $V$ is a vector space over a finite field $K$ of order $q$ such that $dim V>1$, and $m$ is a non-negative integer, then $V$ can be written as a union of $m$ proper subspaces of $V$ if and only if $mgeq q+1$. (From the proof below, it also follows that if $K$ is not finite, then there is no way to cover a vector space $V$ over $K$ with $dim V>1$ by finitely many proper subspaces.)
First suppose that $mgeq q+1$. It suffices to assume that $m=q+1$. Pick a basis $mathcal{B}$ of $V$. Let $a,binmathcal{B}$ be two distinct elements (noting that $|mathcal{B}|>1$ since $dim V>1$). For each $kin K$, we define $V_k$ to be the span of ${a+kb}cupbig(mathcal{B}setminus{a,b}big)$, and $U$ is the span of $mathcal{B}setminus{a}$. Show that
$V=Ucup bigcup_{kin K}V_k$.
Conversely, suppose that $V$ can be written as a union of $m$ proper subspaces $W_1,W_2,ldots,W_m$ with $m$ being smallest possible (from the previous paragraph we know $m$ exists, so taking the smallest one is possible). It is easy to see that $m>1$. By minimality of $m$, for any $i$, we have $W_inotsubseteq bigcup_{jneq i}W_j$.
Take $uin W_1setminusbigcup_{jneq1}W_j$ and $vin W_2setminusbigcup_{jneq 2}W_j$. Since $u+svin V$ for all $sin K$ such that $sneq 0$, we must have $u+svin W_j$ for some $j$. We claim that the assignment $sin Ksetminus{0}$ to the smallest $j$ such that $u+svin W_j$ is an injective function from $Ksetminus{0}$ to ${3,4,ldots,m}$. From here, it follows that $$q-1=big|Ksetminus{0}big|leq big|{3,4,ldots,m}big|=m-2,$$
establishing our claim.
Now, to prove the assertion in the previous paragraph, we first note that $u+svnotin W_1$ and $u+svnotin W_2$ for $sne 0$. If $u+svin W_1$, then $v=s^{-1}big((u+sv)-ubig)in W_1$ since $uin W_1$, which is a contradiction. If $u+svin W_2$, then $u=(u+sv)-svin W_2$ since $vin W_2$, which is also a contradiction. So, $u+svin W_j$ for some $jin{3,4,ldots,m}$.
Now, suppose that there are two non-zero $s,tin K$ such that $u+sv$ and $u+tv$ are in the same $W_i$, where $iin{3,4,ldots,m}$. Then,
$$v=(s-t)^{-1}big((u+sv)-(u+tv)big)in W_i.$$
But $vin W_2setminus bigcup_{jneq 2}W_j$, so we have another contradiction. The assertion is now proven.
add a comment |
We claim that if $V$ is a vector space over a finite field $K$ of order $q$ such that $dim V>1$, and $m$ is a non-negative integer, then $V$ can be written as a union of $m$ proper subspaces of $V$ if and only if $mgeq q+1$. (From the proof below, it also follows that if $K$ is not finite, then there is no way to cover a vector space $V$ over $K$ with $dim V>1$ by finitely many proper subspaces.)
First suppose that $mgeq q+1$. It suffices to assume that $m=q+1$. Pick a basis $mathcal{B}$ of $V$. Let $a,binmathcal{B}$ be two distinct elements (noting that $|mathcal{B}|>1$ since $dim V>1$). For each $kin K$, we define $V_k$ to be the span of ${a+kb}cupbig(mathcal{B}setminus{a,b}big)$, and $U$ is the span of $mathcal{B}setminus{a}$. Show that
$V=Ucup bigcup_{kin K}V_k$.
Conversely, suppose that $V$ can be written as a union of $m$ proper subspaces $W_1,W_2,ldots,W_m$ with $m$ being smallest possible (from the previous paragraph we know $m$ exists, so taking the smallest one is possible). It is easy to see that $m>1$. By minimality of $m$, for any $i$, we have $W_inotsubseteq bigcup_{jneq i}W_j$.
Take $uin W_1setminusbigcup_{jneq1}W_j$ and $vin W_2setminusbigcup_{jneq 2}W_j$. Since $u+svin V$ for all $sin K$ such that $sneq 0$, we must have $u+svin W_j$ for some $j$. We claim that the assignment $sin Ksetminus{0}$ to the smallest $j$ such that $u+svin W_j$ is an injective function from $Ksetminus{0}$ to ${3,4,ldots,m}$. From here, it follows that $$q-1=big|Ksetminus{0}big|leq big|{3,4,ldots,m}big|=m-2,$$
establishing our claim.
Now, to prove the assertion in the previous paragraph, we first note that $u+svnotin W_1$ and $u+svnotin W_2$ for $sne 0$. If $u+svin W_1$, then $v=s^{-1}big((u+sv)-ubig)in W_1$ since $uin W_1$, which is a contradiction. If $u+svin W_2$, then $u=(u+sv)-svin W_2$ since $vin W_2$, which is also a contradiction. So, $u+svin W_j$ for some $jin{3,4,ldots,m}$.
Now, suppose that there are two non-zero $s,tin K$ such that $u+sv$ and $u+tv$ are in the same $W_i$, where $iin{3,4,ldots,m}$. Then,
$$v=(s-t)^{-1}big((u+sv)-(u+tv)big)in W_i.$$
But $vin W_2setminus bigcup_{jneq 2}W_j$, so we have another contradiction. The assertion is now proven.
add a comment |
We claim that if $V$ is a vector space over a finite field $K$ of order $q$ such that $dim V>1$, and $m$ is a non-negative integer, then $V$ can be written as a union of $m$ proper subspaces of $V$ if and only if $mgeq q+1$. (From the proof below, it also follows that if $K$ is not finite, then there is no way to cover a vector space $V$ over $K$ with $dim V>1$ by finitely many proper subspaces.)
First suppose that $mgeq q+1$. It suffices to assume that $m=q+1$. Pick a basis $mathcal{B}$ of $V$. Let $a,binmathcal{B}$ be two distinct elements (noting that $|mathcal{B}|>1$ since $dim V>1$). For each $kin K$, we define $V_k$ to be the span of ${a+kb}cupbig(mathcal{B}setminus{a,b}big)$, and $U$ is the span of $mathcal{B}setminus{a}$. Show that
$V=Ucup bigcup_{kin K}V_k$.
Conversely, suppose that $V$ can be written as a union of $m$ proper subspaces $W_1,W_2,ldots,W_m$ with $m$ being smallest possible (from the previous paragraph we know $m$ exists, so taking the smallest one is possible). It is easy to see that $m>1$. By minimality of $m$, for any $i$, we have $W_inotsubseteq bigcup_{jneq i}W_j$.
Take $uin W_1setminusbigcup_{jneq1}W_j$ and $vin W_2setminusbigcup_{jneq 2}W_j$. Since $u+svin V$ for all $sin K$ such that $sneq 0$, we must have $u+svin W_j$ for some $j$. We claim that the assignment $sin Ksetminus{0}$ to the smallest $j$ such that $u+svin W_j$ is an injective function from $Ksetminus{0}$ to ${3,4,ldots,m}$. From here, it follows that $$q-1=big|Ksetminus{0}big|leq big|{3,4,ldots,m}big|=m-2,$$
establishing our claim.
Now, to prove the assertion in the previous paragraph, we first note that $u+svnotin W_1$ and $u+svnotin W_2$ for $sne 0$. If $u+svin W_1$, then $v=s^{-1}big((u+sv)-ubig)in W_1$ since $uin W_1$, which is a contradiction. If $u+svin W_2$, then $u=(u+sv)-svin W_2$ since $vin W_2$, which is also a contradiction. So, $u+svin W_j$ for some $jin{3,4,ldots,m}$.
Now, suppose that there are two non-zero $s,tin K$ such that $u+sv$ and $u+tv$ are in the same $W_i$, where $iin{3,4,ldots,m}$. Then,
$$v=(s-t)^{-1}big((u+sv)-(u+tv)big)in W_i.$$
But $vin W_2setminus bigcup_{jneq 2}W_j$, so we have another contradiction. The assertion is now proven.
We claim that if $V$ is a vector space over a finite field $K$ of order $q$ such that $dim V>1$, and $m$ is a non-negative integer, then $V$ can be written as a union of $m$ proper subspaces of $V$ if and only if $mgeq q+1$. (From the proof below, it also follows that if $K$ is not finite, then there is no way to cover a vector space $V$ over $K$ with $dim V>1$ by finitely many proper subspaces.)
First suppose that $mgeq q+1$. It suffices to assume that $m=q+1$. Pick a basis $mathcal{B}$ of $V$. Let $a,binmathcal{B}$ be two distinct elements (noting that $|mathcal{B}|>1$ since $dim V>1$). For each $kin K$, we define $V_k$ to be the span of ${a+kb}cupbig(mathcal{B}setminus{a,b}big)$, and $U$ is the span of $mathcal{B}setminus{a}$. Show that
$V=Ucup bigcup_{kin K}V_k$.
Conversely, suppose that $V$ can be written as a union of $m$ proper subspaces $W_1,W_2,ldots,W_m$ with $m$ being smallest possible (from the previous paragraph we know $m$ exists, so taking the smallest one is possible). It is easy to see that $m>1$. By minimality of $m$, for any $i$, we have $W_inotsubseteq bigcup_{jneq i}W_j$.
Take $uin W_1setminusbigcup_{jneq1}W_j$ and $vin W_2setminusbigcup_{jneq 2}W_j$. Since $u+svin V$ for all $sin K$ such that $sneq 0$, we must have $u+svin W_j$ for some $j$. We claim that the assignment $sin Ksetminus{0}$ to the smallest $j$ such that $u+svin W_j$ is an injective function from $Ksetminus{0}$ to ${3,4,ldots,m}$. From here, it follows that $$q-1=big|Ksetminus{0}big|leq big|{3,4,ldots,m}big|=m-2,$$
establishing our claim.
Now, to prove the assertion in the previous paragraph, we first note that $u+svnotin W_1$ and $u+svnotin W_2$ for $sne 0$. If $u+svin W_1$, then $v=s^{-1}big((u+sv)-ubig)in W_1$ since $uin W_1$, which is a contradiction. If $u+svin W_2$, then $u=(u+sv)-svin W_2$ since $vin W_2$, which is also a contradiction. So, $u+svin W_j$ for some $jin{3,4,ldots,m}$.
Now, suppose that there are two non-zero $s,tin K$ such that $u+sv$ and $u+tv$ are in the same $W_i$, where $iin{3,4,ldots,m}$. Then,
$$v=(s-t)^{-1}big((u+sv)-(u+tv)big)in W_i.$$
But $vin W_2setminus bigcup_{jneq 2}W_j$, so we have another contradiction. The assertion is now proven.
edited Nov 23 '18 at 16:00
answered Nov 23 '18 at 12:29
user593746
add a comment |
add a comment |
Hint: If $(x_1,x_2,ldots)in V$ then either $x_1=0$ or there exists $cin K$ with $x_2=cx_1$.
answered Nov 23 '18 at 7:43
Hagen von EitzenHagen von Eitzen
276k21269496
add a comment |
Hint: If $(x_1,x_2,ldots)in V$ then either $x_1=0$ or there exists $cin K$ with $x_2=cx_1$.
answered Nov 23 '18 at 7:43
Hagen von EitzenHagen von Eitzen
276k21269496
add a comment |
Hint: If $(x_1,x_2,ldots)in V$ then either $x_1=0$ or there exists $cin K$ with $x_2=cx_1$.
answered Nov 23 '18 at 7:43
Hagen von EitzenHagen von Eitzen
276k21269496
Hint: If $(x_1,x_2,ldots)in V$ then either $x_1=0$ or there exists $cin K$ with $x_2=cx_1$.
answered Nov 23 '18 at 7:43
Hagen von EitzenHagen von Eitzen
276k21269496
answered Nov 23 '18 at 7:43
Hagen von EitzenHagen von Eitzen
276k21269496
answered Nov 23 '18 at 7:43
Hagen von EitzenHagen von Eitzen
276k21269496
answered Nov 23 '18 at 7:43
Hagen von EitzenHagen von Eitzen
276k21269496
276k21269496
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3010079%2fprove-v-over-finite-field-of-q-elements-can-be-written-as-union-of-q-1-p%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
5
i'd do it first for $dim V=2$.
– Lord Shark the Unknown
Nov 23 '18 at 7:27
3
Pick two linearly independent maps $a, b : V to K$. For each $k in K$, let $V_k = left{v in V mid aleft(vright) = k bleft(vright)right}$. Also, let $V_infty = left{v in V mid bleft(vright) = 0 right}$. Then, $V = V_infty cup bigcup_{k in K} V_k$.
– darij grinberg
Nov 23 '18 at 18:23