How to convert .mkv file into .mp4 file losslessly?

Perhaps the easiest tool for that is ffmpeg, or avconv from the libav-tools package. Libav is a fork of FFmpeg, which Ubuntu switched to for a few years until Ubuntu 15.04. It is one of the backends for many of the GUI tools mentioned in other answers.

Changing container without re-enconding content could not be simpler:

ffmpeg -i input.mkv -codec copy output.mp4

• It auto-detects a Matroska to MP4 container conversion based on input/output filenames.

• -codec copy stream copies, or "re-muxes", the streams from the input to the output without re-encoding. Think of it like a copy and paste.

• Default stream selection behavior is to select only one stream per stream type. For example, if your input has two video streams and one audio stream then only the video stream with the largest frame size will be selected. Add -map 0 if you want to select all streams from the input.

• Some containers may not support some formats. So check if your chosen container format, be it mkv, mp4 or even avi has support for all the content in your files (video, audio, subtitles, data, etc). For example, mp4 does not support SubRip subtitles (.srt files).

Get needed software

sudo apt-get install gpac mkvtoolnix

Extract video and audio from matroska file

First you need to check what tracks the matroska file contains with

mkvmerge --identify video.mkv

File 'video.mkv': container: Matroska
Track ID 1: video (V_MPEG4/ISO/AVC)
Track ID 2: audio (A_AC3)

Then extract video and audio according to their tracks with:

mkvextract tracks video.mkv 1:video.h264 2:audio.ac3

Extracting track 1 with the CodecID 'V_MPEG4/ISO/AVC' to the file 'video.h264'. Container format: AVC/h.264 elementary stream
Extracting track 2 with the CodecID 'A_AC3' to the file 'audio.ac3'. Container format: Dolby Digital (AC3)
Progress: 100%

Mux audio and video into mp4 containter

MP4Box -fps 24 -add video.h264 -add audio.ac3 video.mp4

AVC-H264 import - frame size 1280 x 720 at 24.000 FPS
Import results: 31671 samples - Slices: 5672 I 125048 P 122648 B - 32288 SEI - 4936 IDR
AC3 import - sample rate 48000 - 6 channels
Saving to video.mp4: 0.500 secs Interleaving

I had to add -fps 24 option because MP4Box didn't detect video fps correctly. Depending on usage AC3 audio track should be re-encoded into something else before muxing.

Now you have remuxed streams from matroska container into mp4 container without losing any quality.

EDIT: MP4 doesn't officially support AC3 audio so the audio track should be converted into a supported format (eg. AAC, MP3) if you want the file to be playable with something else than VLC.

You can use Avidemux

It has good GUI interface.

When converting from mkv to mp4 it is not re-encoded.

The convertion is done within a minute (for a 60-min video).

1. sudo apt-get install avidemux

2. Open the mkv file in avidemux.

3. Select safe mode if prompted.

4. Leave the video as copy.

5. Choose File-> Properties. Check if the audio codec is aac.

   1. If audio codec is NOT aac, select aac(faac).
   2. Otherwise, leave it as copy. (Sometimes using this option the audio may be out of sync or distorted, in that case select aac(faac) instead.)

6. Select mp4 for format.

7. Select save, choose location and type a filename with .mp4 as the extension.

Note: Sometimes (~10% chance) it may fail. Then use handbrake(re-encode).

Note2: there are two links which help you:

http://www.ubuntugeek.com/avidemux-free-video-editor-designed-for-simple-cutting-filtering-and-encoding-tasks.html

http://www.ubuntugeek.com/how-to-convert-mkv-file-into-mp4-file-using-avidemux.html