Questions tagged [hermite-normal-form]
The Hermite normal form is an analog of reduced echelon form for matrices over the integers $\mathbb Z$. It can solve problems about the solution to the linear system $Ax=b$ where $x$ is restricted to have integer coordinates only. To be Used with the subject tag [linear-algebra].
17 questions
2
votes
0
answers
47
views
How to Construct an Integer Matrix Whose Submatrices Often Generate $\mathbb{Z}^k$
I encountered the following problem when I tried to design a cryptographic protocol.
Suppose we want to construct a matrix $\mathbf{G} \in \mathbb{Z}^{n \times k}$ with $k \leq n$ such that:
$\mathrm{...
- 249
0
votes
0
answers
57
views
Howell normal form of a $1\times n$ matrix
I'm trying to understand how the Howell normal form of a $1\times n$ matrix over the ring $R=\mathbb{Z}/\mu\mathbb{Z}$ looks like. If I undertand correctly, the only elementary operation allowed in ...
0
votes
1
answer
142
views
Smith normal form of 3x3 matrices
Let $A=\begin{pmatrix}a & d & e\\ 0 & b & f\\ 0 & 0 & c \end{pmatrix}$ be an integer matrix such that $abc=n$, $0 \leq d < b$ and $0 \leq e,f < c$. I'm trying to find an ...
user1278517
2
votes
1
answer
201
views
Counting number of unique $k$-dimensional subspaces over ring of integers mod $p^m$, generated by $VD$, where $D$ is a defined diagonal matrix
I would like to count the number of unique $k$-dimensional subspaces of the form $VD$, where $V\in \text{GL}(n,\mathbb Z/({p^m}))$ is some $n\times n$ matrix defined over the ring of integers modulo $...
- 289
3
votes
1
answer
785
views
To compute Hermite Normal Form H and U
I bounced off this problem now for the third time within a few years.
While there are (a few) sources on the internet, including
wikipedia
a calculator for the Hermite Normal Form
a youtube video on ...
- 133
1
vote
1
answer
436
views
Relationship between Hermite Normal Form and Smith decomposition
Consider a $2\times2$ matrix $P$ with entries in $\mathbb{Z}$ and $\det(P)=N$. Its (row-wise, lower) Hermite Normal Form is given by
$$
H=\begin{pmatrix} d & 0 \\ s & \bar{d}\equiv N/d\end{...
- 105
0
votes
0
answers
124
views
Let $A \in \mathbb{Q}^{m \times n}$ with full row rank. Then the matrix $B$ in $A$’s Hermite Normal Form $[B \quad 0]$ is invertible.
My lecture introduces several new definitions and theorems as below. The part about the matrix $B$ is a passing remark that I’d like to have some more elaboration.
Definition 1. Let $A$ be a $m \...
- 739
1
vote
0
answers
113
views
How to find the general solution using the Hermite polynomial?
I want to solve this equation
$${\frac{1}{(\sqrt{2m})^n}\Bigr(\frac{\hbar}{i}\frac{d}{dx} - im\omega x\Bigr) }^n\psi(x) =0$$
See more about Hermite function recursion relation
$(x-\partial) (e^{x^2/2}\...
- 292
1
vote
1
answer
935
views
cubic Hermite interpolation
Professor gave us this little bastard of a question and I'm at a complete loss about what to do. Some help or hints would be immensely appreciated, translated to the best of my abilities.
Let $x_0=0$,...
- 13
0
votes
1
answer
735
views
Elementary row operations that obtains the Hermite normal form of a matrix.
This article says that the elementary operations required are unimodular transformations. My questions are the following:
Why does it have to be unimodular? What is so special about it?
Why are the ...
- 1,848
1
vote
1
answer
463
views
Hermite Normal Form
Does anyone know an approach to finding the Hermite Normal Form for smaller matrices, like
$
A =\begin{pmatrix}
6 & -6 & 9\\ 3 &2 & 2
\end{pmatrix}
$
Or does one just have to shuffle ...
- 573
3
votes
0
answers
104
views
Hermite normal form of infinite matrix
I have an infinite matrix $A$ that is in row echelon form, except zeros are to the right of each pivot, as shown below. The $*$ symbol denotes any integer, though most of them are zero.
$A= \left( \...
- 474
1
vote
0
answers
198
views
Application to Smith And Hermite Normal Forms
Given $ A $ a $ n\times n $ integer matrix and $ (d_{1},...,d_{n}) $ the diagonal of its Smith Normal Form, I would like to prove that $ \mathbb{Z}^n/Im_{\mathbb{Z}}A\simeq \bigoplus_{i=1}^{n}(\...
- 1,155
0
votes
0
answers
91
views
Reference request for Hermite normal form
I need a reference for the result of Hermite Normal Form of a matrix. I would prefer one which states the result in the following form:
the span of $ k $ $ \mathbb{Z} $-linearly independent vectors ...
- 429
1
vote
1
answer
2k
views
Hermite Normal Form and Reduced Row Echelon form.
After reading about the Hermite Normal form and row echelon form, I find it that both these forms are similar in every respect. My question is, are they similar?
Or is Hermite Normal form a special ...
- 183